We present a number of positive and negative results for variants of the matroid secretary problem. Most notably, we design a constant-factor competitive algorithm for the "random assignment" model where the weights are assigned randomly to the elements of a matroid, and then the elements arrive on-line in an adversarial order (extending a result of Soto Soto11 ). This is under the assumption that the matroid is known in advance. If the matroid is unknown in advance, we present an @math -approximation, and prove that a better than @math approximation is impossible. This resolves an open question posed by BIK07 . As a natural special case, we also consider the classical secretary problem where the number of candidates @math is unknown in advance. If @math is chosen by an adversary from @math , we provide a nearly tight answer, by providing an algorithm that chooses the best candidate with probability at least @math and prove that a probability better than @math cannot be achieved (where @math is the @math -th harmonic number).
in @cite_6 also posed as an open problem whether there is a constant-factor approximation algorithm for the following two models: Assume that a set of @math numerical values are assigned to the matroid elements using a random one-to-one correspondence but that the elements are presented in an adversarial order (AO-RA in our notation). Or, assume that both the assignment of values and the ordering of the elements in the input are random (RO-RA in our notation). The issue of whether the matroid is known beforehand is left somewhat ambiguous in @cite_6 .
@cite_6
2950067834
The most well-known conjecture in the context of matroid secretary problems claims the existence of a constant-factor 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 random (Soto [SODA 2011], Oveis Gharan and Vondr 'ak [ESA 2011]). However, so far, there was no variant of the matroid secretary problem with adversarial weight assignment for which a constant-factor approximation was found. We address this point by presenting a 9-approximation for the , a model suggested shortly after the introduction of the matroid secretary problem, and for which no constant-factor 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 constant-factor approximation has been found for this case, using a clever but rather involved method and analysis (Im and Wang, [SODA 2011]) that leads to a 16000 3-approximation. This is arguably the most involved special case of the matroid secretary problem for which a constant-factor approximation is known. We present a considerably simpler and stronger @math -approximation, based on reducing the problem to a matroid secretary problem on a partition matroid.