Two simplified algorithms for maintaining order in a list

Michael A. Bender; Richard Cole; Erik D. Demaine; Martin Farach-Colton; Jack Zito

doi:10.1007/3-540-45749-6_17

Two simplified algorithms for maintaining order in a list

Michael A. Bender
, Richard Cole
, Erik D. Demaine
, Martin Farach-Colton
, Jack Zito

Computer Science

New York University
Massachusetts Institute of Technology
Alphabet Inc.
Rutgers - The State University of New Jersey, New Brunswick
Stony Brook University

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

131 Scopus citations

Abstract

In the Order-Maintenance Problem, the objective is to maintain a total order subject to insertions, deletions, and precedence queries. Known optimal solutions, due to Dietz and Sleator, are complicated. We present new algorithms that match the bounds of Dietz and Sleator. Our solutions are simple, and we present experimental evidence that suggests that they are superior in practice.

Original language	English
Title of host publication	Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
Editors	Rolf Möhring, Rajeev Raman
Publisher	Springer Verlag
Pages	152-164
Number of pages	13
ISBN (Electronic)	3540441808, 9783540441809
DOIs	https://doi.org/10.1007/3-540-45749-6_17
State	Published - 2002
Event	10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy Duration: Sep 17 2002 → Sep 21 2002

Publication series

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

Conference

Conference	10th Annual European Symposium on Algorithms, ESA 2002
Country/Territory	Italy
City	Rome
Period	09/17/02 → 09/21/02

Access to Document

10.1007/3-540-45749-6_17

Cite this

Bender, M. A., Cole, R., Demaine, E. D., Farach-Colton, M., & Zito, J. (2002). Two simplified algorithms for maintaining order in a list. In R. Möhring, & R. Raman (Eds.), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings (pp. 152-164). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2461). Springer Verlag. https://doi.org/10.1007/3-540-45749-6_17

Bender, Michael A. ; Cole, Richard ; Demaine, Erik D. et al. / Two simplified algorithms for maintaining order in a list. Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. editor / Rolf Möhring ; Rajeev Raman. Springer Verlag, 2002. pp. 152-164 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b82b89b3855448ad961025b64b85d402,

title = "Two simplified algorithms for maintaining order in a list",

abstract = "In the Order-Maintenance Problem, the objective is to maintain a total order subject to insertions, deletions, and precedence queries. Known optimal solutions, due to Dietz and Sleator, are complicated. We present new algorithms that match the bounds of Dietz and Sleator. Our solutions are simple, and we present experimental evidence that suggests that they are superior in practice.",

author = "Bender, \{Michael A.\} and Richard Cole and Demaine, \{Erik D.\} and Martin Farach-Colton and Jack Zito",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 10th Annual European Symposium on Algorithms, ESA 2002 ; Conference date: 17-09-2002 Through 21-09-2002",

year = "2002",

doi = "10.1007/3-540-45749-6\_17",

language = "English",

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

publisher = "Springer Verlag",

pages = "152--164",

editor = "Rolf M{\"o}hring and Rajeev Raman",

booktitle = "Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings",

}

Bender, MA, Cole, R, Demaine, ED, Farach-Colton, M & Zito, J 2002, Two simplified algorithms for maintaining order in a list. in R Möhring & R Raman (eds), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2461, Springer Verlag, pp. 152-164, 10th Annual European Symposium on Algorithms, ESA 2002, Rome, Italy, 09/17/02. https://doi.org/10.1007/3-540-45749-6_17

Two simplified algorithms for maintaining order in a list. / Bender, Michael A.; Cole, Richard; Demaine, Erik D. et al.
Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. ed. / Rolf Möhring; Rajeev Raman. Springer Verlag, 2002. p. 152-164 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2461).

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

TY - GEN

T1 - Two simplified algorithms for maintaining order in a list

AU - Bender, Michael A.

AU - Cole, Richard

AU - Demaine, Erik D.

AU - Farach-Colton, Martin

AU - Zito, Jack

PY - 2002

Y1 - 2002

N2 - In the Order-Maintenance Problem, the objective is to maintain a total order subject to insertions, deletions, and precedence queries. Known optimal solutions, due to Dietz and Sleator, are complicated. We present new algorithms that match the bounds of Dietz and Sleator. Our solutions are simple, and we present experimental evidence that suggests that they are superior in practice.

AB - In the Order-Maintenance Problem, the objective is to maintain a total order subject to insertions, deletions, and precedence queries. Known optimal solutions, due to Dietz and Sleator, are complicated. We present new algorithms that match the bounds of Dietz and Sleator. Our solutions are simple, and we present experimental evidence that suggests that they are superior in practice.

UR - https://www.scopus.com/pages/publications/84938093834

U2 - 10.1007/3-540-45749-6_17

DO - 10.1007/3-540-45749-6_17

M3 - Conference contribution

AN - SCOPUS:84938093834

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

SP - 152

EP - 164

BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings

A2 - Möhring, Rolf

A2 - Raman, Rajeev

PB - Springer Verlag

T2 - 10th Annual European Symposium on Algorithms, ESA 2002

Y2 - 17 September 2002 through 21 September 2002

ER -

Bender MA, Cole R, Demaine ED, Farach-Colton M, Zito J. Two simplified algorithms for maintaining order in a list. In Möhring R, Raman R, editors, Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. Springer Verlag. 2002. p. 152-164. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45749-6_17

Two simplified algorithms for maintaining order in a list

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this