Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
复制标题
提高子模秘书问题的竞争比（扩展摘要）
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Roy Schwartz
中科院分区：
文献类型：
--
作者：
Moran Feldman;J. Naor;Roy Schwartz
古典秘书问题是在20世纪60年代被提出的，没有人知道确切的时间。自引入以来，这个问题的许多变体已经被提出和研究。在经典秘书问题及其许多变体中，输入（即一组秘书或元素）以随机顺序到达。在本文中，我们将一个简单的观察应用于秘书问题，该观察表明，输入的随机顺序可以通过独立选择每个秘书的随机连续到达时间来生成。令人惊讶的是，这个简单的观察使我们能够提高几个已知和研究过的秘书问题变体的竞争比。此外，在某些情况下，与现有的证明相比，我们提供的假设随机到达时间的证明更短、更简单。在本文中，我们考虑了秘书问题的三种变体，它们都具有相同的目标，即给定单调子模函数f，使所选秘书集的值最大化。在第一种变体中，我们只允许雇用一组秘书，当它是给定划分矩阵的独立集时。第二个变体允许我们选择最多k个秘书的任意集合。在最后一种和第三种变体中，我们可以雇用满足给定背包约束的任何一组秘书。
The Classical Secretary Problem was introduced during the 60’s of the 20 th century, nobody is sure exactly when. Since its introduction, many variants of the problem have been proposed and researched. In the classical secretary problem, and many of its variant, the input (which is a set of secretaries, or elements) arrives in a random order. In this paper we apply to the secretary problem a simple observation which states that the random order of the input can be generated by independently choosing a random continuous arrival time for each secretary. Surprisingly, this simple observation enables us to improve the competitive ratio of several known and studied variants of the secretary problem. In addition, in some cases the proofs we provide assuming random arrival times are shorter and simpler in comparison to existing proofs. In this work we consider three variants of the secretary problem, all of which have the same objective of maximizing the value of the chosen set of secretaries given a monotone submodular function f. In the first variant we are allowed to hire a set of secretaries only if it is an independent set of a given partition matroid. The second variant allows us to choose any set of up to k secretaries. In the last and third variant, we can hire any set of secretaries satisfying a given knapsack constraint.