Theory Lunch Seminar

— 1:00pm

In Person - Gates Hillman 8102

SANDER BORST , Computer Science Department, Carnegie Mellon University

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:

Add event to Google
Add event to iCal