Pinning down the strong wilber 1 bound for binary search trees

Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

16 Lataukset (Pure)

Abstrakti

The 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. Despite extensive work and some notable progress, including, for example, the Tango Trees (Demaine et al., FOCS 2004), that give the best currently known O(log log n)-competitive algorithm, the conjecture remains widely open. One of the main hurdles towards settling the conjecture is that we currently do not have approximation algorithms achieving better than an O(log log n)-approximation, even in the offline setting. All known non-trivial algorithms for BST's so far rely on comparing the algorithm's cost with the so-called Wilber's first 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 two-fold. First, we show that the gap between the WB-1 bound and the optimal solution value can be as large as Ω(log log n/log log log n); in fact, we show that the gap holds even for several stronger variants of the bound. Second, we provide a simple algorithm, that, given an integer D > 0, obtains an O(D)-approximation in time exp ( O (n1/2Ω(D) log n )). In particular, this yields a constant-factor approximation algorithm with sub-exponential running time. Moreover, we obtain a simpler and cleaner efficient O(log log n)-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.

AlkuperäiskieliEnglanti
OtsikkoApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020
ToimittajatJaroslaw Byrka, Raghu Meka
KustantajaSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Sivumäärä21
ISBN (elektroninen)9783959771641
DOI - pysyväislinkit
TilaJulkaistu - 1 elokuuta 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
Tapahtuma23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation (APPROX/RANDOM) - Virtual, Online, Yhdysvallat
Kesto: 17 elokuuta 202019 elokuuta 2020

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
KustantajaSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Vuosikerta176
ISSN (painettu)1868-8969

Conference

Conference23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation (APPROX/RANDOM)
Maa/AlueYhdysvallat
KaupunkiVirtual, Online
Ajanjakso17/08/202019/08/2020

Sormenjälki

Sukella tutkimusaiheisiin 'Pinning down the strong wilber 1 bound for binary search trees'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä