Theory Seminar

An Optimal Binary Search Tree?

Seth Pettie, PhD., Assistant Professor, EECS
WHEN:
Thursday, September 28, 2006 @ 4:30 pm
Add to Google Calendar
WEB: Event Website
SHARE:

Dynamic Optimality—Almost

Erik D. Demaine † Dion Harmon John Iacono† Mihai Patra scu

Abstract

We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous(trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan’s dynamic optimality conjecture of 1985 that O(1)-competitive binary search trees exist.

Sponsored by

Theory Faculty