The ACO Seminar (2018–2019)

Consider the task of performing a sequence of searches in a binary search tree. After each search, an algorithm is allowed to arbitrarily restructure the tree, at a cost proportional to the amount of restructuring performed. The cost of an algorithm’s execution is the sum of the time spent searching and the time spent optimizing those searches with restructuring operations. This notion was introduced by Sleator and Tarjan in 1985, along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments while moving searched items to the top of the tree. The conjecture, called Dynamic Optimality, is that the cost of splaying is always within a constant factor of the optimal algorithm for performing searches. The conjecture stands to this day.

I will present the first systematic proposal for how to settle the dynamic optimality conjecture.

Joint work with Bob Tarjan.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.