%% Theory of Computing
%% File: v019a008.bib
%% Publication date: December 19, 2023
%% Authors: Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak
%
%
%
@ARTICLE {avl,
AUTHOR = {Adel'son-Vel'skii, Georgii Maksimovich and Landis, Evgenii Mikhailovich},
TITLE = {An algorithm for organization of information},
JOURNAL = doklady,
VOLUME = {146},
number = {2},
YEAR = {1962},
PAGES = {263--266},
note  = {\href{https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26964&option_lang=eng}{Math-Net.ru}},
}
%
@ARTICLE{Bayer1972,
author    = {Rudolf Bayer},
title = {Symmetric Binary {B}-Trees: {D}ata Structure and Maintenance Algorithms},
journal   = ActaInf,
year      = {1972},
volume    = {1},
number    = 4,
pages     = {290--306},
doi       = {10.1007/BF00289509},
}
%
%
@article{BoseDIL14,
author = {Prosenjit Bose and Karim Dou{\"{\i}}eb and John Iacono and
      Stefan Langerman},
title={The Power and Limitations of Static Binary Search Trees with
      Lazy Finger},
journal = algorithmica,
year = {2016},
volume = {76},
pages     = {1264--1275},
doi = {10.1007/s00453-016-0224-x},
note={\prelim \href{https://doi.org/10.1007/978-3-319-13075-0\_15}{ISAAC'14}},
}
%
@INPROCEEDINGS{BoseDIL14-conf,
author  = {Prosenjit Bose and Karim Dou{\"{\i}}eb and John Iacono and Stefan Langerman},
title   = {The Power and Limitations of Static Binary Search Trees with Lazy Finger},
crossref = {pisaac14},
pages     = {181--192},
doi   = {10.1007/978-3-319-13075-0\_15},
}

@INPROCEEDINGS{conf-version,
author = {Parinya Chalermsook and Julia Chuzhoy and Thatchaphol Saranurak},
title =	{Pinning down the Strong {W}ilber 1 Bound for Binary Search Trees},
crossref  = {papprox20},
pages =	{33:1--21},
doi =	{10.4230/LIPIcs.APPROX/RANDOM.2020.33},
}

@InProceedings{our_wads,
author= {Chalermsook, Parinya and Goswami, Mayank and Kozma, L{\'a}szl{\'o} and
Mehlhorn, Kurt and Saranurak, Thatchaphol},
title= {Greedy Is an Almost Optimal Deque},
crossref = {pwads15},
pages= {152--165},
doi = {10.1007/978-3-319-21840-3\_13},
}

@INPROCEEDINGS{FOCS15,
author    = {Parinya Chalermsook and Mayank Goswami and L{\'{a}}szl{\'{o}} Kozma and
Kurt Mehlhorn and Thatchaphol Saranurak},
title     = {Pattern-Avoiding Access in Binary Search Trees},
crossref  = {pfocs15},
pages     = {410--423},
doi  =  {10.1109/FOCS.2015.32},
eprint    = {1507.06953},
}
%
@ARTICLE{chaudhuri,
author = {Chaudhuri, Ranjan and H\"{o}ft, Hartmut F.},
title = {Splaying a Search Tree in Preorder Takes Linear Time},
journal = sigactnews,
year  = {1993},
volume = {24},
number = {2},
pages = {88--93},
doi = {10.1145/156063.156067},
}
%
@Article{finger2,
Title   = {{On the Dynamic Finger Conjecture for splay trees. Part II: The proof}},
Author                   = {Cole, Richard},
Journal                  = sicomp,
Year                     = {2000},
Volume                   = {30},
Number                   = {1},
Pages                    = {44-85},
doi  = {10.1137/S009753979732699X},
}

@Article{finger1,
Title = {{On the Dynamic Finger Conjecture for splay trees. Part I: Splay}
Sorting $\log n$-Block Sequences},
Author={Cole, Richard and Mishra, Bud and Schmidt, Jeanette and Siegel, Alan},
Journal  = sicomp,
Year     = {2000},
Volume   = {30},
Number   = {1},
Pages    = {1--43},
doi  = {10.1137/S0097539797326988},
}

@BOOK{cormen2022introduction,
title={Introduction to Algorithms},
author={Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford},
year={2022},
publisher={MIT press},
note = {\href{http://mitpress.mit.edu/9780262046305/introduction-to-algorithms}{MIT Press}},
}

@INPROCEEDINGS{DHIKP09,
author    = {Erik D. Demaine and Dion Harmon and John Iacono and Daniel M. Kane         and Mihai {P\v{a}tra\c{s}cu}},
title     = {The geometry of binary search trees},
crossref  = {psoda09},
pages     = {496--505},
note      = {\href{https://dl.acm.org/doi/10.5555/1496770.1496825}{ACM DL}},
}
%
@ARTICLE{tango,
author    = {Erik D. Demaine and Dion Harmon and John Iacono and
Mihai {P\v{a}tra\c{s}cu}},
title     = {Dynamic Optimality--Almost},
journal   = sicomp,
volume    = {37},
number    = {1},
pages     = {240--251},
year      = {2007},
doi       = {10.1137/S0097539705447347},
note      = {\prelim \href{https://doi.org/10.1109/FOCS.2004.23}{FOCS'04}},
}
%
@techreport{DSW,
title={A lower bound framework for binary search trees with rotations},
author={Derryberry, Jonathan C. and Sleator, Daniel Dominic and Wang, Chengwen Chris},
year={2005},
institution = {CMU-CS-05-187},
note = {Available on \href{https://www.cs.cmu.edu/~jonderry/lower-bound.pdf}{author's website}},
}
%
@Inproceedings{DS09,
Title = {Skip-Splay: {T}oward Achieving the Unified Bound in the {BST} Model},
Author  = {Derryberry, Jonathan C. and Sleator, Daniel Dominic},
crossref  = {pwads09},
Pages     = {194--205},
doi = {10.1007/978-3-642-03367-4\_18}
}

@Article{deque_Elm04,
Title={On the sequential access theorem and deque conjecture for splay trees},
Author      = {Amr Elmasry},
Journal     = tcs,
Year        = {2004},
Volume      = {314},
Number      = {3},
Pages       = {459--466},
Doi         = {10.1016/j.tcs.2004.01.019},
}

@Article{chain_splay,
Title = {Chain-splay trees, or, how to achieve and prove
        {$\log\log N$}-competitiveness by splaying},
Author                   = {George F. Georgakopoulos},
Journal                  = ipl,
Year                     = {2008},
Volume                   = {106},
Number                   = {1},
Pages                    = {37--43},
doi = {10.1016/j.ipl.2007.10.001},
}
%
@PHDTHESIS{Harmon,
author       = {Dion Harmon},
title        = {New Bounds on Optimal Binary Search Trees},
school       = {MIT},
year         = 2006,
note={\href{https://dspace.mit.edu/bitstream/handle/1721.1/34268/71014527-MIT.pdf}{MIT}},
}
%
@InCollection{in_pursuit,
Title        = {In Pursuit of the Dynamic Optimality Conjecture},
Author       = {Iacono, John},
Booktitle    = {Space-Efficient Data Structures, Streams, and Algorithms},
Editor  = {Brodnik, A. and López-Ortiz, A. and Raman, V. and Viola, A.},
Publisher    = springer,
Year         = {2013},
Pages        = {236--250},
Series       = {LNCS},
Volume       = {8066},
doi  = {10.1007/978-3-642-40273-9\_16},
}

@INPROCEEDINGS{IL-lazy,
title={Weighted dynamic finger in binary search trees},
author={Iacono, John and Langerman, Stefan},
crossref = {psoda16},
pages = {672--691},
doi = {10.1137/1.9781611974331.ch49},
}

@PHDTHESIS{Kozma16_thesis,
author    = {L\'aszl\'o Kozma},
title     = {Binary search trees, rectangles and patterns},
school    = {Saarland University, Saarbr{\"{u}}cken, Germany},
year      = {2016},
note={\href{http://scidok.sulb.uni-saarland.de/volltexte/2016/6646/}{Saarland U.}},
}

@InProceedings{LW19,
author =	{Victor Lecomte and Omri Weinstein},
title =	{Settling the Relationship Between {W}ilber’s Bounds for Dynamic Optimality},
crossref = {pesa20},
pages =	{68:1--21},
doi =		{10.4230/LIPIcs.ESA.2020.68},
eprint = {1912.02858},
}

@INPROCEEDINGS{LevyT19,
author    = {Caleb C. Levy and Robert E. Tarjan},
title     = {A New Path from Splay to Dynamic Optimality},
crossref  = {psoda19},
pages     = {1311--1330},
doi = {10.1137/1.9781611975482.80},
}
%
%
%
@incollection{split_Luc91,
Title = {On the competitiveness of splay trees: {R}elations to the union-find problem},
Author = {Joan M. Lucas},
booktitle = {On-line Algorithms},
series = {DIMACS Ser. in Discrete Math. and Theor. Comp. Sci.},
editor = {Lyle A. McGeoch and Daniel D. Sleator},
Year   = {1992},
Volume = {7},
Pages  = {95--124},
publisher = ams,
doi = {10.1090/dimacs/007},
}
%
@InProceedings{deque_Pet08,
Title = {Splay Trees, {D}avenport-{S}chinzel Sequences, and the
         {D}eque {C}onjecture},
Author  = {Pettie, Seth},
crossref = {psoda08},
Pages    = {1115--1124},
doi      = {10.5555/1347082.1347204},
eprint   = {0707.2160},
}
%
@ARTICLE{ST85,
author    = {Daniel Dominic Sleator and Robert Endre Tarjan},
title     = {Self-Adjusting Binary Search Trees},
journal   = jacm,
volume    = {32},
number    = {3},
pages     = {652--686},
year      = {1985},
doi       = {10.1145/3828.3835},
note    = {\prelim \href{https://doi.org/10.1145/800061.808752}{STOC'83}},
}

@Article{deque_Sun92,
Title  = {On the {D}eque {C}onjecture for the splay algorithm},
Author = {Sundar, Rajamani},
Journal = cca,
Year    = {1992},
Number  = {1},
Pages   = {95--124},
Volume  = {12},
Doi     = {10.1007/BF01191208},
}

@Article{Tar85,
Title  = {Sequential access in splay trees takes linear time},
Author = {Tarjan, Robert Endre},
Journal = cca,
Year    = {1985},
Volume  = {5},
Number  = {4},
Pages   = {367--378},
doi     = {10.1007/BF02579253},
}

@InProceedings{multisplay,
Title  = {{$\mathrm{O}(\log \log N)$}-competitive Dynamic Binary Search Trees},
Author = {Wang, Chengwen C. and Derryberry, Jonathan C. and
          Sleator, Daniel Dominic},
crossref = {psoda06},
Pages    = {374--383},
note = {\href{https://dl.acm.org/doi/10.5555/1109557.1109600}{ACM DL}},
}
%
%
@ARTICLE{wilber,
author = {Wilber, Robert E.},
title = {Lower Bounds for Accessing Binary Search Trees with Rotations},
journal = sicomp,
volume = {18},
number = {1},
pages = {56-67},
year = {1989},
doi = {10.1137/0218004},
note = {\prelim \href{https://doi.org/10.1109/SFCS.1986.28}{FOCS'86}},
}
