The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems
The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems
复制标题
DOI：
10.1007/s00224-015-9642-4
复制
发表时间：
2011-07
影响因子：
0.5
通讯作者：
Tengyu Ma;Bo Tang;Yajun Wang
中科院分区：
文献类型：
--
作者：
Tengyu Ma;Bo Tang;Yajun Wang
研究了具有子模赋值函数的拟阵秘书问题。在这些问题中，元素以随机顺序到达。当一个元素到达时，我们必须立即做出不可撤销的决定是否接受它。被接受的元素的集合必须在一个预定义的拟阵中形成一个独立的集合。我们的目标是最大限度地提高已接受元素的价值。本文主要研究赋值函数为非负单调非减次模函数的情形。本文介绍了这类次模拟阵秘书问题的一般算法。特别是，我们得到的情况下，层拟阵和横截拟阵的常数竞争算法。我们的算法可以进一步应用于任何独立的集系统定义的constantnumber的层状拟阵的交集，同时仍然实现恒定的竞争比。注意，层拟阵推广了一致拟阵和划分拟阵。另一方面，当底层赋值函数是线性的，我们的算法实现了一个竞争比为9.6层拟阵，这显着改善了以前的结果。
We study the matroid secretary problems with submodular valuation functions. In these problems, the elements arrive in random order. When one element arrives, we have to make an immediate and irrevocable decision on whether to accept it or not. The set of accepted elements must form anindependent setin a predefined matroid. Our objective is to maximize the value of the accepted elements. In this paper, we focus on the case that the valuation function is a non-negative and monotonically non-decreasing submodular function. We introduce a general algorithm for suchsubmodular matroid secretary problems. In particular, we obtain constant competitive algorithms for the cases of laminar matroids and transversal matroids. Our algorithms can be further applied to any independent set system defined by the intersection of aconstantnumber of laminar matroids, while still achieving constant competitive ratios. Notice that laminar matroids generalize uniform matroids and partition matroids. On the other hand, when the underlying valuation function is linear, our algorithm achieves a competitive ratio of 9.6 for laminar matroids, which significantly improves the previous result.