Static optimality and dynamic search-optimality in lists and trees
Lists
Only you see this
Abstract
Adaptive data structures form a central topic of on-line algorithms research, beginning 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 [ST85a, ST85b]. This paper is inspired by the observation that one can in fact achieve a 1 + ε ratio against the best static object in hindsight for a wide range of data structure problems via "weighted experts" techniques from Machine Learning, if computational decision-making costs are not considered.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 simultaneously achieve good static and dynamic bounds. Second, for trees, we show a (computationally inefficient) algorithm that achieves what we call "dynamic search optimality": dynamic optimality if we allow the online 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.
BibTeX
@inproceedings{blum2003static,
author = {Avrim Blum and Shuchi Chawla and Adam Kalai},
title = {{Static optimality and dynamic search-optimality in lists and trees}},
booktitle = {Algorithmica},
year = {2003},
url = {https://openreview.net/forum?id=JdZR6gwxmff},
}Loading related content...