During the last 15 years online algorithms have received considerable research interest. In
this survey we give an introduction to the competitive analysis of online algorithms and …

This chapter surveys results in the design and analysis of self-organizing data structures for
the search problem. The general search problem in pointer data structures can be phrased …

The advice model of online computation captures the setting in which the online algorithm is
given some information concerning the request sequence. This paradigm allows to establish …

The best randomized on-line algorithms known so far for the list update problem achieve a
competitiveness of 3≈1.73. In this paper we present a new family of randomized on-line …

We prove upper and lower bounds on the competitiveness of randomized algorithms for the
list update problem of Sleator and Tarjan. We give a simple and elegant randomized …

We present a randomized on-line algorithm for the list update problem which achieves a
competitive factor of 1.6, the best known so far. The algorithm makes an initial random …

T UG $ V" W" X% Y4' BWa 0 cb sca'B8¦ E § 58A@ 0¥ $'4¡© § ¤ 18¦@ Hd § ¤£ dCG CF CE
CG CF CE C¦ CE C¦ CE C¦ CE CF CG CE CF CG CF C afe scR g¥ h£ G@ § ©@ G¥ $# x …

We suggest a simple modification to the Kd-tree search algorithm for nearest neighbor
search resulting in an improved performance. The Kd-tree data structure seems to work well …

There has been considerable effort to prove lower bounds for the competitiveness of a
randomized list update algorithm. Lower bounds of 1.18 and (by a numerical technique) …

This paper concerns the online list accessing problem. In the first part of the paper we
present two new families of list accessing algorithms. The first family is of optimal, 2 …