论文标题
候选名单的子模型秘书秘书问题
Submodular Matroid Secretary Problem with Shortlists
论文作者
论文摘要
在Matroid秘书问题中，Matroid $ \ Mathcal {M} $的元素按随机顺序到达。一旦观察到一个项目，我们就需要不可撤销地决定是否接受它。选定元素的集合应形成独立的矩阵集。目标是最大化分配给这些元素的值的总和。 我们介绍了[Agrawal等人]中的候选名单模型动机的一个版本。在此设置中，允许算法作为候选名单的一部分选择项目子集，可能超过$ k = rk（\ Mathcal {M}）$项目。然后，在看到整个输入后，算法可以从候选名单中选择一个独立的子集。此外，我们将目标函数推广到任何单调的下一个函数。在线算法是否使用大小$ o（k）$的入围名单实现恒定的竞争比率？我们设计了一种实现$ \ frac {1} {2}（1-1/e^2-ε-o（1/k））$的算法，对于任何常数$ε> 0 $，使用大小$ o（k）$的竞争比率。考虑到Matroid秘书问题最著名的竞争比率为$ O（\ log \ log k）$，这尤其令人惊讶。 我们的算法的一个重要应用是用于下函数的随机顺序流。我们证明我们的算法可以使用$ O（k）$内存在流设置中实现。它实现了$ \ frac {1} {2}（1-1/e^2-ε-o（1/k））$近似值。由于[Feldman等人]，[Chekuri等人]和[Chakrabarti等人]，先前最著名的近似值近似值近似值近似值为0.25（对抗秩序）。此外，我们将结果概括为p匹配的约束，并给出了$ \ frac {1} {p+1}（1-1/e^{p+1}-ε-o（1/k））$近似值，使用$ o（k）$ bemorme $ o（k）$ normantottottical nrline Capithing offline保证$ \ frac $ \ frac} $ n nrline Busine of the Offline保证。
In the matroid secretary problem, the elements of a matroid $\mathcal{M}$ arrive in random order. Once we observe an item we need to irrevocably decide whether or not to accept it. The set of selected elements should form an independent set of the matroid. The goal is to maximize the total sum of the values assigned to these elements. We introduce a version of this problem motivated by the shortlist model in [Agrawal et al.]. In this setting, the algorithm is allowed to choose a subset of items as part of a shortlist, possibly more than $k=rk(\mathcal{M})$ items. Then, after seeing the entire input, the algorithm can choose an independent subset from the shortlist. Furthermore we generalize the objective function to any monotone submodular function. Is there an online algorithm achieve a constant competitive ratio using a shortlist of size $O(k)$? We design an algorithm that achieves a $\frac{1}{2}(1-1/e^2-ε-O(1/k))$ competitive ratio for any constant $ε>0$, using a shortlist of size $O(k)$. This is especially surprising considering that the best known competitive ratio for the matroid secretary problem is $O(\log \log k)$. An important application of our algorithm is for the random order streaming of submodular functions. We show that our algorithm can be implemented in the streaming setting using $O(k)$ memory. It achieves a $\frac{1}{2}(1-1/e^2-ε-O(1/k))$ approximation. The previously best known approximation ratio for streaming submodular maximization under matroid constraint is 0.25 (adversarial order) due to [Feldman et al.], [Chekuri et al.], and [Chakrabarti et al.]. Moreover, we generalize our results to the case of p-matchoid constraints and give a $\frac{1}{p+1}(1-1/e^{p+1}-ε-O(1/k))$ approximation using $O(k)$ memory, which asymptotically approaches the best known offline guarantee $\frac{1}{p+1}$ [Nemhauser et al.]
