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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 484-490 |
| Number of pages | 7 |
| Journal | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
| State | Published - 2004 |
| Event | Proceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 - Rome, Italy Duration: Oct 17 2004 → Oct 19 2004 |
ASJC Scopus subject areas
- General Engineering