Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pǎtraşcu, “Dynamic Optimality—Almost”, SIAM Journal on Computing, volume 37, number 1, May 2007, pages 240–251. Special issue of selected papers from the 45th Annual IEEE Symposium on Foundations of Computer Science.

BibTeX

@Article{Tango_SICOMP,
  AUTHOR        = {Erik D. Demaine and Dion Harmon and John Iacono and
                   Mihai P\v{a}tra\c{s}cu},
  TITLE         = {Dynamic Optimality---Almost},
  JOURNAL       = {SIAM Journal on Computing},
  journalurl    = {http://www.siam.org/journals/sicomp/sicomp.htm},
  VOLUME        = 37,
  NUMBER        = 1,
  PAGES         = {240--251},
  MONTH         = {May},
  YEAR          = 2007,
  NOTE          = {Special issue of selected papers from the 45th Annual IEEE
                   Symposium on Foundations of Computer Science.},

  doi           = {https://dx.doi.org/10.1137/S0097539705447347},
  dblp          = {https://dblp.org/rec/journals/siamcomp/DemaineHIP07},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1137/S0097539705447347">SIAM</A>.},
  updates       = {There is a typo on page 7, last paragraph: <i>A</i> should be the tree with nodes of <i>smaller</i> depth.},
  length        = {12 pages},
  withstudent   = 1,
  papers        = {Tango_FOCS2004},
  replaces      = {Tango_FOCS2004},
}

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.

Comments:

This paper is also available from SIAM.

Updates:

There is a typo on page 7, last paragraph: A should be the tree with nodes of smaller depth.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (364k), gzipped PostScript (154k), and PDF (206k).

See information on file formats.

[Google Scholar search]

Related papers:

Tango_FOCS2004 (Dynamic Optimality—Almost)