LIPIcs.ESA.2020.68.pdf
- Filesize: 0.58 MB
- 21 pages
Document
Settling the Relationship Between Wilber’s Bounds for Dynamic Optimality
Authors
-
Part of:
Volume:
28th Annual European Symposium on Algorithms (ESA 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-08-26
File
Document Identifiers
Acknowledgements
We want to thank the anonymous reviewers for their enthusiastic feedback and the numerous typos they spotted.
Cite As Get BibTex
Victor Lecomte and Omri Weinstein. Settling the Relationship Between Wilber’s Bounds for Dynamic Optimality. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 68:1-68:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.68
Abstract
In FOCS 1986, Wilber proposed two combinatorial lower bounds on the operational cost of any binary search tree (BST) for a given access sequence X ∈ [n]^m. Both bounds play a central role in the ongoing pursuit of the dynamic optimality conjecture (Sleator and Tarjan, 1985), but their relationship remained unknown for more than three decades. We show that Wilber’s Funnel bound dominates his Alternation bound for all X, and give a tight Θ(lg lg n) separation for some X, answering Wilber’s conjecture and an open problem of Iacono, Demaine et. al. The main ingredient of the proof is a new symmetric characterization of Wilber’s Funnel bound, which proves that it is invariant under rotations of X. We use this characterization to provide initial indication that the Funnel bound matches the Independent Rectangle bound (Demaine et al., 2009), by proving that when the Funnel bound is constant, IRB_upRect is linear. To the best of our knowledge, our results provide the first progress on Wilber’s conjecture that the Funnel bound is dynamically optimal (1986).
Subject Classification
ACM Subject Classification
- Theory of computation → Data structures design and analysis
Keywords
- data structures
- binary search trees
- dynamic optimality
- lower bounds
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Brian Allen and Ian Munro. Self-organizing binary search trees. J. ACM, 25(4):526-535, October 1978. URL: https://doi.org/10.1145/322092.322094.
- Prosenjit Bose, Karim Douïeb, Vida Dujmovic, and Rolf Fagerberg. An O(log log n)-competitive binary search tree with optimal worst-case access times. In Algorithm Theory - SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings, pages 38-49, 2010. URL: https://doi.org/10.1007/978-3-642-13731-0_5.
- Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak. Pinning down the strong wilber 1 bound for binary search trees. CoRR, abs/1912.02900, 2019. URL: http://arxiv.org/abs/1912.02900.
- Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Pattern-avoiding access in binary search trees. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 410-423. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.32.
- Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, and Mihai Patrascu. The geometry of binary search trees. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 496-505, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496825.
- Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Patrascu. Dynamic optimality - almost. SIAM J. Comput., 37(1):240-251, 2007. URL: https://doi.org/10.1137/S0097539705447347.
- John Iacono. Key-independent optimality. Algorithmica, 42(1):3-10, 2005. URL: https://doi.org/10.1007/s00453-004-1136-8.
- John Iacono. 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, pages 236-250, 2013. URL: https://doi.org/10.1007/978-3-642-40273-9_16.
- László Kozma and Thatchaphol Saranurak. Smooth heaps and a dual view of self-adjusting data structures. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 801-814, 2018. URL: https://doi.org/10.1145/3188745.3188864.
- Victor Lecomte and Omri Weinstein. Settling the relationship between wilber’s bounds for dynamic optimality. CoRR, abs/1912.02858, 2019. URL: http://arxiv.org/abs/1912.02858.
- Caleb C. Levy and Robert E. Tarjan. A new path from splay to dynamic optimality. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1311-1330. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.80.
-
Joan Marie Lucas. Canonical forms for competitive binary search tree algorithms. Rutgers University, Department of Computer Science, Laboratory for Computer Science Research, 1988.
- J. Ian Munro. On the competitiveness of linear search. In Mike Paterson, editor, Algorithms - ESA 2000, 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000, Proceedings, volume 1879 of Lecture Notes in Computer Science, pages 338-345. Springer, 2000. URL: https://doi.org/10.1007/3-540-45253-2_31.
- Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652-686, July 1985. URL: https://doi.org/10.1145/3828.3835.
- Chengwen Chris Wang, Jonathan Derryberry, and Daniel Dominic Sleator. O(log log n)-competitive dynamic binary search trees. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06, pages 374-383, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1109557.1109600.
- R. Wilber. Lower bounds for accessing binary search trees with rotations. SIAM J. Comput., 18(1):56-67, February 1989. URL: https://doi.org/10.1137/0218004.