## Abstract

Suppose that k mobile servers are located on a circle. Repeatedly, a request at a point x on the circle appears. To serve this request one of the servers has to be moved to x. The cost of moving a server to x is the distance on the circle between the server's previous location and x. The decision which server to move has to be done on-line; that is, without the knowledge of future requests. We give a deterministic on-line algorithm for making these decisions. Our algorithm is O(k^{3})-competitive: for any sequence of requests, the cost incurred by our algorithm in serving this sequence is bounded (up to an additive constant) by O(k^{3}) times the cost of serving this sequence using the best off-line algorithm; i.e., an algorithm that has a priori knowledge of the whole sequence. Our algorithm is the best deterministic constructive algorithm for k>2.

Original language | English |
---|---|

Pages (from-to) | 572-578 |

Number of pages | 7 |

Journal | Algorithmica |

Volume | 11 |

Issue number | 6 |

DOIs | |

State | Published - Jun 1994 |

Externally published | Yes |

## Keywords

- On-line algorithms
- k-Server problem

## Fingerprint

Dive into the research topics of 'A deterministic O(k^{3})-competitive k-server algorithm for the circle'. Together they form a unique fingerprint.