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).
@cite_6: We study a generalization of the classical secretary problem which we call the "matroid secretary problem". In this problem, the elements of a matroid are presented to an online algorithm in random order. When an element arrives, the algorithm observes its value and must make an irrevocable decision regarding whether or not to accept it. The accepted elements must form an independent set, and the objective is to maximize the combined value of these elements. This paper presents an O(log k)-competitive algorithm for general matroids (where k is the rank of the matroid), and constant-competitive algorithms for several special cases including graphic matroids, truncated partition matroids, and bounded degree transversal matroids. We leave as an open question the existence of constant-competitive algorithms for general matroids. Our results have applications in welfare-maximizing online mechanism design for domains in which the sets of simultaneously satisfiable agents form a matroid.
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 .