Skip to main navigation Skip to search Skip to main content

A nearly optimal randomized algorithm for explorable heap selection

  • Sander Borst
  • , Daniel Dadush*
  • , Sophie Huiberts
  • , Danish Kashaev
  • *Corresponding author for this work
  • Centrum voor Wiskunde en Informatica
  • Columbia University

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

Explorable heap selection is the problem of selecting the nth 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·exp(O(logn)) time algorithms using O(log(n)2.5) and O(logn) space respectively. We present a new randomized algorithm with running time O(nlog(n)3) against an oblivious adversary using O(logn) 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))) lower bound for any algorithm that solves the problem in the same amount of space, indicating that our algorithm is nearly optimal.

Original languageEnglish
Pages (from-to)75–96
Number of pages22
JournalMathematical Programming
Volume210
Issue number1
Early online date5 Nov 2024
DOIs
Publication statusPublished - 2025

Bibliographical note

Publisher Copyright:
© The Author(s) 2024.

Funding

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement QIP-805241).

FundersFunder number
European Research Council (ERC)QIP-805241

    Keywords

    • 90C57
    • Branch and bound
    • Graph exploration
    • Node selection
    • Online algorithm

    Fingerprint

    Dive into the research topics of 'A nearly optimal randomized algorithm for explorable heap selection'. Together they form a unique fingerprint.

    Cite this