Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence
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.
Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997
David L. Shealy, John A. Hoffnagle
SPIE Optical Engineering + Applications 2007