Static optimality and dynamic search-optimality in lists and trees
Avrim L. Blum, Shuchi Chawla, Adam Tauman Kalai · 2002
Abstract. Adaptive data structures form a central topic of on-line algorithms research. The area of Competitive Analysis began with the results of Sleator and Tarjan showing that splay trees achieve static optimality for search trees, and that Move-to-Front is constant competitive for the list update problem [ST1], [ST2]. In a parallel development, powerful algorithms have been developed in Machine Learning for problems of on-line prediction [LW], [FS]. This paper is inspired by the observation made in [BB] that if computational decision-making costs are not considered, then these “weighted experts ” techniques from Machine Learning allow one to achieve a 1 + ε ratio against the best static object in hindsight for a wide range of data structure problems. In this paper we give two results. First, we show that for the case of lists, we can achieve a 1 + ε ratio with respect to the best static list in hindsight, by a simple efficient algorithm. This algorithm can then be combined with existing results to achieve good static and dynamic bounds simultaneously. Second, for trees, we show a (computationally inefficient) algorithm that achieves what we call “dynamic search optimality”: dynamic optimality if we allow the on-line algorithm to make free rotations after each request. We hope this to be a step towards solving the longstanding open problem of achieving true dynamic optimality for trees.