| dc.description.abstract | The matroid secretary problem admits several variants according to the order in
which the matroid’s elements are presented and how the elements are assigned weights. As the
main result of this article, we devise the first constant competitive algorithm for the model in which
both the order and the weight assignment are selected uniformly at random, achieving a competitive
ratio of approximately 5.7187. This result is based on the nontrivial fact that every matroid can
be approximately decomposed into uniformly dense minors. Based on a preliminary version of
this work, Oveis Gharan and Vondr´ak [Proceedings of the 19th Annual European Symposium on
Algorithms, ESA, 2011, pp. 335–346] devised a 40e/(e − 1)-competitive algorithm for the stronger
random-assignment adversarial-order model. In this article we present an alternative algorithm
achieving a competitive ratio of 16e/(e −1). As additional results, we obtain new algorithms for the
standard model of the matroid secretary problem: the adversarial-assignment random-order model.
We present an O(log r)-competitive algorithm for general matroids which, unlike previous ones, uses
only comparisons among seen elements. We also present constant competitive algorithms for various
matroid classes, such as column-sparse representable matroids and low-density matroids. The latter
class includes, as a special case, the duals of graphic matroids. | |
