The general two-server problem
René A. Sitters, Leen Stougie · TU/e Research Portal · 2003
Abstract. We consider the general on-line two-server problem in which at each step both servers receive a request, which is a point in a metric space. One of the servers has to be moved to its request. The special case where the requests are points on the real line is known as the CNN-problem. It has been a famous 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 sense by providing the first constant competitive algorithm for the general two-server problem on any metric space. The basic result in this paper is a characterization of competitiveness for metrical service systems that seems much easier to use when looking for a competitive algorithm. The ex-istence of a competitive algorithm for the general two-server problem follows rather easily from this result. 1