Technical Report CS0880

Title: A $(4k+1)$-Competitive Algorithm for the $k$-server with fixed cost excursion problem
Authors: Y. Hollander and A. Itai
PDFNot 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.
CopyrightThe 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 (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1996
To the main CS technical reports page

Computer science department, Technion