A nearly optimal randomized algorithm for explorable heap selection

DOI10.1007/S10107-024-02145-5MaRDI QIDQ7019076zbMATH OpenFDO

Authors Daniel Dadush, Sophie Huiberts, Danish Kashaev

Publication date 5 March 2025

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

online algorithmbranch-and-boundgraph explorationnode selection

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Randomized algorithms (68W20) Combinatorial optimization (90C27) Searching and sorting (68P10)

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
• A nearly optimal randomized algorithm for explorable heap selection
• 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
• Constructing competitive tours from local information
• Exploration of graphs with excluded minors
• On learning and branching: a survey
• On the best search strategy in parallel branch-and-bound: Best-first search versus lazy depth-first search
• Online graph exploration: New results on old and new algorithms
• Probability and Computing
• SCIP: solving constraint integer programs
• Selection and sorting with limited storage
• The theory of search games and rendezvous.
• Tree exploration with little memory

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 Q7019076)