In pursuit of the dynamic optimality conjecture

John Iacono

doi:10.1007/978-3-642-40273-9_16

In pursuit of the dynamic optimality conjecture

John Iacono

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotation-based search tree algorithm on every sufficiently long sequence - any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal. Here we survey the progress that has been made in the almost thirty years since the conjecture was first formulated, and present a binary search tree algorithm that is dynamically optimal if any binary search tree algorithm is dynamically optimal.

Original language	English (US)
Title of host publication	Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday
Publisher	Springer Verlag
Pages	236-250
Number of pages	15
ISBN (Print)	9783642402722
DOIs	https://doi.org/10.1007/978-3-642-40273-9_16
State	Published - 2013
Event	Conference on Space-Efficient Data Structures, Streams, and Algorithms - Waterloo, ON, Canada Duration: Aug 15 2013 → Aug 16 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8066 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	Conference on Space-Efficient Data Structures, Streams, and Algorithms
Country/Territory	Canada
City	Waterloo, ON
Period	8/15/13 → 8/16/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-40273-9_16

Cite this

Iacono, J. (2013). In pursuit of the dynamic optimality conjecture. In Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday (pp. 236-250). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8066 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-40273-9_16

In pursuit of the dynamic optimality conjecture. / Iacono, John.
Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Springer Verlag, 2013. p. 236-250 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8066 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Iacono, J 2013, In pursuit of the dynamic optimality conjecture. in Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8066 LNCS, Springer Verlag, pp. 236-250, Conference on Space-Efficient Data Structures, Streams, and Algorithms, Waterloo, ON, Canada, 8/15/13. https://doi.org/10.1007/978-3-642-40273-9_16

Iacono J. In pursuit of the dynamic optimality conjecture. In Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Springer Verlag. 2013. p. 236-250. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40273-9_16

@inproceedings{b7e0ff1dbc784ae79e09373fb8512e6e,

title = "In pursuit of the dynamic optimality conjecture",

abstract = "In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotation-based search tree algorithm on every sufficiently long sequence - any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal. Here we survey the progress that has been made in the almost thirty years since the conjecture was first formulated, and present a binary search tree algorithm that is dynamically optimal if any binary search tree algorithm is dynamically optimal.",

author = "John Iacono",

year = "2013",

doi = "10.1007/978-3-642-40273-9_16",

language = "English (US)",

isbn = "9783642402722",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "236--250",

booktitle = "Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday",

note = "Conference on Space-Efficient Data Structures, Streams, and Algorithms ; Conference date: 15-08-2013 Through 16-08-2013",

}

TY - GEN

T1 - In pursuit of the dynamic optimality conjecture

AU - Iacono, John

PY - 2013

Y1 - 2013

N2 - In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotation-based search tree algorithm on every sufficiently long sequence - any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal. Here we survey the progress that has been made in the almost thirty years since the conjecture was first formulated, and present a binary search tree algorithm that is dynamically optimal if any binary search tree algorithm is dynamically optimal.

AB - In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotation-based search tree algorithm on every sufficiently long sequence - any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal. Here we survey the progress that has been made in the almost thirty years since the conjecture was first formulated, and present a binary search tree algorithm that is dynamically optimal if any binary search tree algorithm is dynamically optimal.

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

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

U2 - 10.1007/978-3-642-40273-9_16

DO - 10.1007/978-3-642-40273-9_16

M3 - Conference contribution

AN - SCOPUS:84894143514

SN - 9783642402722

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 236

EP - 250

BT - Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday

PB - Springer Verlag

T2 - Conference on Space-Efficient Data Structures, Streams, and Algorithms

Y2 - 15 August 2013 through 16 August 2013

ER -

In pursuit of the dynamic optimality conjecture

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this