Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pǎtraşcu, “Dynamic Optimality—Almost”, in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), Rome, Italy, October 17–19, 2004, pages 484–490.

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.

Length:

The paper is 7 pages.

Availability:

The paper is available in PostScript (164k), gzipped PostScript (66k), and PDF (88k).

See information on file formats.

[Google Scholar search]

Related papers:

Tango_SICOMP (Dynamic Optimality—Almost)