2013 | OriginalPaper | Chapter
Advances on Matroid Secretary Problems: Free Order Model and Laminar Case
Authors : Patrick Jaillet, José A. Soto, Rico Zenklusen
Published in: Integer Programming and Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The best-known conjecture in the context of matroid secretary problems claims the existence of an
O
(1)-approximation applicable to any matroid. Whereas this conjecture remains open, modified forms of it were shown to be true, when assuming that the assignment of weights to the secretaries is not adversarial but uniformly at random [20,18]. However, so far, no variant of the matroid secretary problem with adversarial weight assignment is known that admits an
O
(1)-approximation. We address this point by presenting a 9-approximation for the
free order model
, a model suggested shortly after the introduction of the matroid secretary problem, and for which no
O
(1)-approximation was known so far. The free order model is a relaxed version of the original matroid secretary problem, with the only difference that one can choose the order in which secretaries are interviewed.
Furthermore, we consider the classical matroid secretary problem for the special case of laminar matroids. Only recently, a
O
(1)-approximation has been found for this case, using a clever but rather involved method and analysis [12] that leads to a 16000/3-approximation. This is arguably the most involved special case of the matroid secretary problem for which an
O
(1)-approximation is known. We present a considerably simpler and stronger
$3\sqrt{3}e\approx 14.12$
-approximation, based on reducing the problem to a matroid secretary problem on a partition matroid.