论文标题
一种几乎最佳的随机算法，用于探索堆选择
A nearly optimal randomized algorithm for explorable heap selection
论文作者
论文摘要
可探索的堆选择是在二进制堆中选择$ n $第三最小值的问题。只能通过穿过潜在的无限二进制树来访问钥匙值，并且算法的复杂性通过树中传播的总距离来衡量（每个边缘都有单位成本）。最初提出了这个问题作为研究分支机构算法的搜索策略的模型，Karp，saks and saks and widgerson（focs '86）的存储限制，他们提供了确定性和随机$ n \ cdot \ exp \ exp（o（o（\ sqrt {n} n}} n} n}）$ 2. $ o（\ sqrt {\ log n}）$ space。我们使用$ o（\ log n）$空间提出了一种新的随机时间$ o（n \ log（n）^3）$的新随机算法，从而实质上改善了以前的最佳随机运行时间，而牺牲了略有增加的空间使用情况。对于任何在相同量的空间中解决问题的算法，我们还显示$ω（\ log（n）n/\ log（\ log（n）））$ $，表明我们的算法几乎是最佳的。
Explorable heap selection is the problem of selecting the $n$th smallest value in a binary heap. The key values can only be accessed by traversing through the underlying infinite binary tree, and the complexity of the algorithm is measured by the total distance traveled in the tree (each edge has unit cost). This problem was originally proposed as a model to study search strategies for the branch-and-bound algorithm with storage restrictions by Karp, Saks and Widgerson (FOCS '86), who gave deterministic and randomized $n\cdot \exp(O(\sqrt{\log{n}}))$ time algorithms using $O(\log(n)^{2.5})$ and $O(\sqrt{\log n})$ space respectively. We present a new randomized algorithm with running time $O(n\log(n)^3)$ using $O(\log n)$ space, substantially improving the previous best randomized running time at the expense of slightly increased space usage. We also show an $Ω(\log(n)n/\log(\log(n)))$ for any algorithm that solves the problem in the same amount of space, indicating that our algorithm is nearly optimal.
