A competitive algorithm for the general 2-server problem

R.A. Sitters, L. Stougie, W.E. Paepe, de

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)


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 well-known open question 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.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming (Proceedings 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003)
EditorsJ.C.M. Baeten, J.K. Lenstra, J. Parrow, G.J. Woeginger
Place of PublicationBerlin
ISBN (Print)3-540-40493-7
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'A competitive algorithm for the general 2-server problem'. Together they form a unique fingerprint.

Cite this