Pinning Down the Strong Wilber-1 Bound for Binary Search Trees

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.