Algorithms, Combinatorics and Optimization Seminar
— 4:30pm
Location:
8220
-
Wean Hall
Speaker:
CALEB C. LEVY
,
Ph.D. Candidate
https://www.pacm.princeton.edu/people/caleb-levy
A New Path from Splay to Dynamic Optimality
Speaker: Caleb C. Levy
Location: Wean 8220
A New Path from Splay to Dynamic Optimality
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.
Faculty Host: Danny Sleator
3:10 pm: Pre-Talk Refreshments, Wean Hall 6220
Event Website:
http://aco.math.cmu.edu/abs-18-19/oct18.html