A (4k+1)-Competitive Algorithm for the K-Server With Fixed Cost Excursion Problem

Let M be a metric space on which we have k servers. A request is a point oe 2 M and is serviced either by moving a server to oe, with cost equal to the distance the server moved, or by conducting an excursion, with cost fi (smaller than this distance). Our aim is to service (on-line) any sequence oe = oe 1 ; : : : ; oe f of requests. An on-line algorithm is c-competitive if for every sequence oe 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 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