Dynamic optimality - Almost

Erik D. Demaine; Dion Harmon; John Iacono; Mihai Pǎtraşcu

doi:10.1137/S0097539705447347

Dynamic optimality - Almost

Erik D. Demaine, Dion Harmon, John Iacono, Mihai Pǎtraşcu

Research output: Contribution to journal › Article › peer-review

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)	240-251
Number of pages	12
Journal	SIAM Journal on Computing
Volume	37
Issue number	1
DOIs	https://doi.org/10.1137/S0097539705447347
State	Published - 2007

Keywords

Binary search trees
Competitiveness
Splay trees

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/S0097539705447347

Cite this

@article{c85dc4a646ca45698ab17f2a0a084863,

title = "Dynamic optimality - Almost",

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.",

keywords = "Binary search trees, Competitiveness, Splay trees",

author = "Demaine, {Erik D.} and Dion Harmon and John Iacono and Mihai Pǎtra{\c s}cu",

year = "2007",

doi = "10.1137/S0097539705447347",

language = "English (US)",

volume = "37",

pages = "240--251",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - Dynamic optimality - Almost

AU - Demaine, Erik D.

AU - Harmon, Dion

AU - Iacono, John

AU - Pǎtraşcu, Mihai

PY - 2007

Y1 - 2007

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

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

KW - Binary search trees

KW - Competitiveness

KW - Splay trees

UR - http://www.scopus.com/inward/record.url?scp=40049109344&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=40049109344&partnerID=8YFLogxK

U2 - 10.1137/S0097539705447347

DO - 10.1137/S0097539705447347

M3 - Article

AN - SCOPUS:40049109344

SN - 0097-5397

VL - 37

SP - 240

EP - 251

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 1

ER -

Dynamic optimality - Almost

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this