Algorithms, Combinatorics and Optimization Seminar

Thursday, October 18, 2018 - 3:30pm to 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

For More Information, Contact:

Keywords:

Seminar