### Abstract

We consider the generalized on-line two-server problem in which each server moves in its own metric space. Requests for service arrive one-by-one and every request is represented by two points: one in each metric space. The problem is to move, at every request, one of the two servers to its request-point such that the total distance travelled by the two servers is minimized.The special case in which both metric spaces are the real line is known as the CNN-problem. It has been a well-known open question in on-line optimization if an algorithm with a constant-competitive ratio exists for this problem. We answer this question in the affirmative by providing a constant-competitive algorithm for the generalized two-server problem on any metric space.The basic result in this article is a characterization of competitiveness for metrical service systems that seems much easier to use when looking for a competitive algorithm. The existence of a competitive algorithm for the generalized two-server problem follows rather easily from this result.

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

Pages (from-to) | 437-458 |

Journal | Journal of the ACM |

Volume | 53 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2006 |

## Fingerprint Dive into the research topics of 'The generalized two-server problem'. Together they form a unique fingerprint.

## Cite this

Sitters, R. A., & Stougie, L. (2006). The generalized two-server problem.

*Journal of the ACM*,*53*(3), 437-458. https://doi.org/10.1145/1147954.1147960