MATROID SECRETARY PROBLEM IN THE RANDOM-ASSIGNMENT MODEL

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.