On variants of the matroid secretary problem

Abstract

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, SODA 2011, pp. 1275-1284, 2011). This is under the assumption that the matroid is known in advance. If the matroid is unknown in advance, we present an O(logrlogn)-approximation, and prove that a better than O(logn/loglogn) approximation is impossible. This resolves an open question posed by Babaioff et al. (SODA 2007, pp. 434-443, 2007). As a natural special case, we also consider the classical secretary problem where the number of candidates n is unknown in advance. If n is chosen by an adversary from {1,.,N}, we provide a nearly tight answer, by providing an algorithm that chooses the best candidate with probability at least 1/(H N-1+1) and prove that a probability better than 1/H N cannot be achieved (where H N is the N-th harmonic number). © 2013 Springer Science+Business Media New York.