论文标题
改进的秘书秘书问题有候选名单
Improved Submodular Secretary Problem with Shortlists
论文作者
论文摘要
首先，对于候选名单[1]的subsodular $ k $ - 秘书问题，我们使用尺寸$ o（k poly（1/ε））$的候选名单提供了接近最佳的$ 1-1/e-ε$近似。特别是，我们从$ o（k 2^{poly（1/ε）}）$提高了\ cite {us}中使用的候选名单的大小到$ o（k poly（k poly（1/ε））$。结果，我们使用内存$ O（k poly（1/ε））$提供了一种接近最佳的近似算法，用于在基数约束下单调下一个功能的随机流算法。它以$ 1/ε$的方式呈指数级改善\ cite {us}的运行时间和内存。 接下来，我们将问题概括为矩形约束，我们将其称为候选名单中的子模拟秘书问题。它是\ textIt {Matroid秘书问题} \ cite {feldman2014simple}的变体，其中允许算法具有候选名单。我们设计了一种实现$ \ frac {1} {2} {2}（1-1/e^2-ε）$竞争比的算法，使用$ o（k poly（\ frac {1}ε））的候选时间为任何常数$ε> 0 $。此外，我们将结果推广到$ p $ - 摩匹差约束的情况下，并给出$ \ frac {1} {p+1}（1-1/e^{p+1}-ε）$使用size $ o（k poly（\ frac {1}}ε））$近似。它渐近地接近最著名的离线保证$ \ frac {1} {p+1} $ [22]。此外，我们表明我们的算法可以使用$ o（k poly（\ frac {1}ε））$内存在流设置中实现。
First, for the for the submodular $k$-secretary problem with shortlists [1], we provide a near optimal $1-1/e-ε$ approximation using shortlist of size $O(k poly(1/ε))$. In particular, we improve the size of shortlist used in \cite{us} from $O(k 2^{poly(1/ε)})$ to $O(k poly(1/ε))$. As a result, we provide a near optimal approximation algorithm for random-order streaming of monotone submodular functions under cardinality constraints, using memory $O(k poly(1/ε))$. It exponentially improves the running time and memory of \cite{us} in terms of $1/ε$. Next we generalize the problem to matroid constraints, which we refer to as submodular matroid secretary problem with shortlists. It is a variant of the \textit{matroid secretary problem} \cite{feldman2014simple}, in which the algorithm is allowed to have a shortlist. We design an algorithm that achieves a $\frac{1}{2}(1-1/e^2 -ε)$ competitive ratio for any constant $ε>0$, using a shortlist of size $O(k poly(\frac{1}ε))$. Moreover, we generalize our results to the case of $p$-matchoid constraints and give a $\frac{1}{p+1}(1-1/e^{p+1}-ε)$ approximation using shortlist of size $O(k poly(\frac{1}ε))$. It asymptotically approaches the best known offline guarantee $\frac{1}{p+1}$ [22]. Furthermore, we show that our algorithms can be implemented in the streaming setting using $O(k poly(\frac{1}ε))$ memory.
