A nearly optimal randomized algorithm for explorable heap selection

DOI10.1007/978-3-031-32726-1_3MaRDI QIDQ6085985zbMATH OpenOpenAlexFDO

Authors Daniel Dadush, Sophie Huiberts, Danish Kashaev

Publication date 9 November 2023

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.05982

zbMATH Keywords

smallest value in a binary heap

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: 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 $ncdotexp(O(sqrtlogn))$ time algorithms using $O(log(n{)}^{2.5})$ and $O(sqrtlogn)$ space respectively. We present a new randomized algorithm with running time $O(nlog(n{)}^3)$ using $O(logn)$ space, substantially improving the previous best randomized running time at the expense of slightly increased space usage. We also show an $Omega(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.

Recommendations

• An optimal algorithm for selection in a min-heap
• Selection from read-only memory with limited workspace
• Selection from read-only memory with limited workspace
• scientific article; zbMATH DE number 742986
• scientific article; zbMATH DE number 140493

Cites work

• A Computational Study of Search Strategies for Mixed Integer Programming
• A fast LU update for linear programming
• A near optimal algorithm for the extended cow-path problem in the presence of relative errors
• An optimal algorithm for selection in a min-heap
• Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
• Branching rules revisited
• Models and algorithms for online exploration and search.
• On learning and branching: a survey
• On the best search strategy in parallel branch-and-bound: Best-first search versus lazy depth-first search
• SCIP: solving constraint integer programs
• Selection and sorting with limited storage
• Space-Efficient Parallel Algorithms for Combinatorial Search Problems
• The theory of search games and rendezvous.
• Tree exploration with little memory

Cited in

(1)

• A nearly optimal randomized algorithm for explorable heap selection

This page was built for publication: A nearly optimal randomized algorithm for explorable heap selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6085985)