Context-Based Algorithms for the List-Update Problem under Alternative Cost Models∗

Abstract: The List-Update Problem is a well studied online problem with di-rect applications in data compression. Although the model proposed by Sleator & Tarjan [16] has become the standard in the field for the problem, its appli-cability in some domains, and in particular for compression purposes, has been questioned. In this paper, we focus on two alternative models for the prob-lem that arguably have more practical significance than the standard model. We provide new algorithms for these models, and show that these algorithms outperform all classical algorithms under the discussed models. This is done via an empirical study of the performance of these algorithms on the reference data set for the list-update problem. The presented algorithms make use of the context-based strategies for compression, which have not been considered before in the context of the list-update problem and lead to improved compres-sion algorithms. In addition, we study the adaptability of these algorithms to different measures of locality of reference and compressibility.