期刊
SIAM JOURNAL ON COMPUTING
卷 42, 期 1, 页码 178-211出版社
SIAM PUBLICATIONS
DOI: 10.1137/110852061
关键词
secretary problems; matroids; principal partition; online selection
资金
- NSF [CCF-0829878]
- ONR [N00014-05-1-0148]
- Nucleo Milenio Informacion y Coordinacion en Redes [ICM/FIC P10-024F]
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 Vondrak [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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据