Improved competitive ratio for the matroid secretary problem
Improved competitive ratio for the matroid secretary problem
复制标题
DOI：
10.1137/1.9781611973099.135
复制
发表时间：
2012-01
期刊：
影响因子：
--
通讯作者：
Sourav Chakraborty;Oded Lachish
中科院分区：
文献类型：
--
作者：
Sourav Chakraborty;Oded Lachish
Babaioff等人（2007）提出的拟阵秘书问题是经典秘书问题的推广。在这个问题中，从拟阵的元素是在一个随机的顺序提供给在线算法。每个元素都有一个与之相关联的权重，该权重与元素一起沿着给算法。在每个元素被揭示之后，算法必须做出是否选择它的不可撤销的决定。目标是选择一个独立的集合，其权重之和尽可能大。Babaioff等人给出了一个竞争比为O（logρ）的拟阵秘书问题的算法，其中ρ是拟阵的秩。它已被证实，一个恒定的竞争比是可以实现的这个问题。本文给出了一个竞争比为O（logρ）的算法。
The Matroid Secretary Problem, introduced by Babaioff et al. (2007), is a generalization of the Classical Secretary Problem. In this problem, elements from a matroid are presented to an on-line algorithm in a random order. Each element has a weight associated with it, which is revealed to the algorithm along with the element. After each element is revealed the algorithm must make an irrevocable decision on whether or not to select it. The goal is to pick an independent set with the sum of the weights of the selected elements as large as possible. Babaioff et al gave an algorithm for the Matroid Secretary Problem with a competitive ratio of O(logρ), where ρ is the rank of the matroid. It has been conjectured that a constant competitive-ratio is achievable for this problem. In this paper we give an algorithm that has a competitive-ratio of O(√logρ).