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). In this talk I will argue that this online problem is related to node selection in branch and bound, and describe nearly optimal upper and lower bounds on its complexity.

Bio:

Sophie Huiberts is a Simons Fellow at Columbia University in New York. Her research focuses on practical algorithms for solving integer programming problems, specifically on theoretically analyzing them. She did her PhD research at Centrum Wiskunde & Informatica in Amsterdam and received the Stieltjes Prize for best mathematics PhD thesis in the Netherlands.