A Nearly Optimal Randomized Algorithm for Explorable Heap Selection.

Sander Borst Daniel Dadush Sophie Huiberts Danish Kashaev

Published in: IPCO (2023)

Keyphrases

randomized algorithm
dynamic programming
data structure
lower bound
greedy algorithm
optimal solution
competitive ratio
randomized algorithms
worst case
search space
upper bound
sufficient conditions
weighted sum