Publication View

Dynamic Optimality–Almost (2008)

Erik D. Demaine,
Dion Harmon,
John Iacono

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. 1.

Publication details

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=?doi=10.1.1.126.7339
Source	http://db.uwaterloo.ca/~eddemain/papers/Tango_FOCS2004/paper.pdf
Contributors	CiteSeerX
Repository	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Type	text
Language	English
Relation	10.1.1.36.2713, 10.1.1.49.9930, 10.1.1.21.4124, 10.1.1.131.3774, 10.1.1.121.6918, 10.1.1.86.9954, 10.1.1.83.2320, 10.1.1.83.8253, 10.1.1.117.2812, 10.1.1.83.1128, 10.1.1.85.1267