loading...
Dynamic Optimality — Almost
Rome, Italy October 17-October 19
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.2345th Annual IEEE Symposium on Foundat ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Erik D. Demaine, Dion Harmon, John Iacono, Mihai Pătraşcu, "Dynamic Optimality — Almost," Foundations of Computer Science, Annual IEEE Symposium on, pp. 484-490, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2004.23,
author = {Erik D. Demaine and Dion Harmon and John Iacono and Mihai Pătraşcu},
title = {Dynamic Optimality — Almost},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2004},
issn = {0272-5428},
pages = {484-490},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.23},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - Dynamic Optimality — Almost
SN - 0272-5428
SP484
EP490
A1 - Erik D. Demaine,
A1 - Dion Harmon,
A1 - John Iacono,
A1 - Mihai Pătraşcu,
PY - 2004
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Erik D. Demaine, Massachusetts Institute of Technology
Dion Harmon, Massachusetts Institute of Technology
John Iacono, Polytechnic University
Mihai Pătraşcu, Massachusetts Institute of Technology
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.
Citation:
Erik D. Demaine, Dion Harmon, John Iacono, Mihai Pătraşcu, "Dynamic Optimality — Almost," focs, pp.484-490, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.