%0 Journal Article %A Blum, Avrim %A Chawla, Shuchi %A Kalai, Adam %D 1985 %T Static Optimality and Dynamic Search-Optimality in Lists and Trees %U https://kilthub.cmu.edu/articles/journal_contribution/Static_Optimality_and_Dynamic_Search-Optimality_in_Lists_and_Trees/6609875 %R 10.1184/R1/6609875.v1 %2 https://kilthub.cmu.edu/ndownloader/files/12102014 %K Adaptive data structures %K Binary search trees %K Competitive Analysis %K Experts Analysis. %X 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. %I Carnegie Mellon University