# Technical Report CS0880

 TR#: CS0880 Class: CS Title: A $(4k+1)$-Competitive Algorithm for the $k$-server with fixed cost excursion problem Authors: Y. Hollander and A. Itai PDF Not Available Abstract: Let $m$ be a metric space on which we have $k$ servers. A {\em request} is a point $\sigma \in M$ and is serviced either by moving a server to $\sigma$, with cost equal to the distance the server moved, or by conducting an {\em excursion}, with cost $\beta$ (smaller than this distance). Our aim is to service (on-line) any sequence $\sigma=\sigma_1,...,\sigma_f$ of requests. An on-line algorithm is $c$-competitive if for every sequence $\sigma$ the cost of the on-line algorithm is at most $c$ times the cost of the optimal off-line algorithm plus an additive factor. This paper adapts the {\em work function algorithm} of Koutsoupias and Papadimitriou [10], for the $k$-server problem (with no excursions) to handle also excursions. The resulting algorithm is \$(4k+1)-competitive. We show that our problem is a generalization of the bypass problem that arises in the context of paging of memory cache, and thus obtain a competitive algorithm for that problem too. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1996/CS/CS0880), rather than to the URL of the PDF files directly. The latter URLs may change without notice.