Pinning Down the Strong Wilber-1 Bound for Binary Search Trees
Loading...
Access rights
openAccess
CC BY
CC BY
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2023-12-19
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
THEORY OF COMPUTING, Volume 19, issue 8, pp. 1-71
Abstract
Dynamic Optimality Conjecture, postulating the existence of an O(1)-competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems in dynamic data structures. The conjecture remains wide open, despite extensive work and some notable progress, including, for example, the O(loglogn)-competitive Tango Trees, which is the best currently known competitive ratio. One of the main hurdles towards settling the conjecture is that we currently do not have polynomial-time approximation algorithms achieving better than an O(loglogn)-approximation, even in the offline setting. All known non-trivial algorithms for BSTs rely on comparing the algorithm's cost with the so-called Wilber-1 bound (WB-1). Therefore, establishing the worst-case relationship between this bound and the optimal solution cost appears crucial for further progress, and it is an interesting open question in its own right. Our contribution is twofold. First, we show that the gap between WB-1 and the optimal solution value can be as large as Ω(loglogn/logloglogn) ; in fact, we show that the gap holds even for several stronger variants of the bound.∗ Second, we show, given an integer D>0, a D-approximation algorithm that runs in time exp(O(n1/2Ω(D)logn)). In particular, this yields a constant-factor approximation algorithm with subexponential running time.∗∗ Moreover, we obtain a simpler and cleaner efficient O(loglogn)-approximation algorithm that can be used in an online setting. Finally, we suggest a new bound, that we call the Guillotine Bound, that is stronger than WB-1, while maintaining its algorithm-friendly nature, that we hope will lead to better algorithms. All our results use the geometric interpretation of the problem, leading to cleaner and simpler analysis.Description
| openaire: EC/H2020/759557/EU//ALGOCom
Keywords
Other note
Citation
Chalermsook, P, Chuzhoy, J & Saranurak, T 2023, ' Pinning Down the Strong Wilber-1 Bound for Binary Search Trees ', THEORY OF COMPUTING, vol. 19, no. 8, 8, pp. 1-71 . < https://theoryofcomputing.org/articles/v019a008/ >