A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
复制标题
DOI：
10.1137/1.9781611973730.79
复制
发表时间：
2014-04
期刊：
影响因子：
--
通讯作者：
Moran Feldman;O. Svensson;R. Zenklusen
中科院分区：
文献类型：
--
作者：
Moran Feldman;O. Svensson;R. Zenklusen
直到最近，针对矩阵秘书问题的O（log（秩））竞争性算法才取得了进展。更确切地说，Chakraborty 和 Lachish（2012 年）提出了一个 O([EQUATION]log(rank)) - 竞争程序，而 Lachish（2014 年）最近提出了一个 O(log log (rank)) - 竞争算法。这两种算法都涉及复杂的分析。通过使用不同的工具，我们提出了一种更为简单的 O（对数 log（秩））竞争算法。我们的算法可以解释为一种简单的矩阵秘书算法分布，易于分析。我们还能极大地改进竞争比中的隐藏常数。
Only recently progress has been made in obtaining o(log(rank))-competitive algorithms for the matroid secretary problem. More precisely Chakraborty and Lachish (2012) presented a O([EQUATION]log(rank))-competitive procedure, and Lachish (2014) recently presented a O(log log (rank))-competitive algorithm. Both algorithms are involved with complex analyses. Using different tools, we present a considerably simpler O(log log(rank))-competitive algorithm. Our algorithm can be interpreted as a distribution over a simple type of matroid secretary algorithms which are easy to analyze. We are also able to vastly improve on the hidden constant in the competitive ratio.