Theory Lunch Seminar
— 1:00pm
Location:
In Person
-
Gates Hillman 8102
Speaker:
SANDER BORST
,
Computer Science Department, Carnegie Mellon University
https://sanderborst.nl/
Selection in Explorable Heaps
The problem of finding the nth smallest number in a collection is known as the selection problem. But what if the collection of numbers is not directly accessible to us? This is what explorable heap selection is about. It is the problem of selecting the nth smallest value in a binary heap, where the values can only be accessed by traversing the binary tree. In this setting we want to minimize the distance traveled in the tree. The problem was originally proposed by Karp, Saks and Widgerson (FOCS '86), who also proposed algorithms for this problem. Recently we found a new algorithm, that significantly improves on the running time. In this talk I will explain the problem, our new algorithm and the connection between the problem and the branch-and-bound algorithm for solving integer programs.
The Theory Lunch Seminar is supported in part by Smart Contract Research Forum
CMU Theory Youtube Channel
Event Website:
https://www.cs.cmu.edu/~theorylunch/