Static Optimality and Dynamic Search‐Optimality in Lists and Trees

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 in efficient) 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.