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

10 Citations (Scopus)

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 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
PublisherSpringer
Pages624-636
ISBN (Print)3-540-40493-7
DOIs
Publication statusPublished - 2003

Publication series

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

Fingerprint

Server
Metric space
Competitive Ratio
Real Line

Cite this

Sitters, R. A., Stougie, L., & Paepe, de, W. E. (2003). A competitive algorithm for the general 2-server problem. In J. C. M. Baeten, J. K. Lenstra, J. Parrow, & G. J. Woeginger (Eds.), Automata, Languages and Programming (Proceedings 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003) (pp. 624-636). (Lecture Notes in Computer Science; Vol. 2719). Berlin: Springer. https://doi.org/10.1007/3-540-45061-0_50
Sitters, R.A. ; Stougie, L. ; Paepe, de, W.E. / A competitive algorithm for the general 2-server problem. Automata, Languages and Programming (Proceedings 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003). editor / J.C.M. Baeten ; J.K. Lenstra ; J. Parrow ; G.J. Woeginger. Berlin : Springer, 2003. pp. 624-636 (Lecture Notes in Computer Science).
@inproceedings{c9186009dbef43a18c22e7c0f3fa3a5e,
title = "A competitive algorithm for the general 2-server problem",
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 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.",
author = "R.A. Sitters and L. Stougie and {Paepe, de}, W.E.",
year = "2003",
doi = "10.1007/3-540-45061-0_50",
language = "English",
isbn = "3-540-40493-7",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "624--636",
editor = "J.C.M. Baeten and J.K. Lenstra and J. Parrow and G.J. Woeginger",
booktitle = "Automata, Languages and Programming (Proceedings 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003)",
address = "Germany",

}

Sitters, RA, Stougie, L & Paepe, de, WE 2003, A competitive algorithm for the general 2-server problem. in JCM Baeten, JK Lenstra, J Parrow & GJ Woeginger (eds), Automata, Languages and Programming (Proceedings 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003). Lecture Notes in Computer Science, vol. 2719, Springer, Berlin, pp. 624-636. https://doi.org/10.1007/3-540-45061-0_50

A competitive algorithm for the general 2-server problem. / Sitters, R.A.; Stougie, L.; Paepe, de, W.E.

Automata, Languages and Programming (Proceedings 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003). ed. / J.C.M. Baeten; J.K. Lenstra; J. Parrow; G.J. Woeginger. Berlin : Springer, 2003. p. 624-636 (Lecture Notes in Computer Science; Vol. 2719).

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

TY - GEN

T1 - A competitive algorithm for the general 2-server problem

AU - Sitters, R.A.

AU - Stougie, L.

AU - Paepe, de, W.E.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

U2 - 10.1007/3-540-45061-0_50

DO - 10.1007/3-540-45061-0_50

M3 - Conference contribution

SN - 3-540-40493-7

T3 - Lecture Notes in Computer Science

SP - 624

EP - 636

BT - Automata, Languages and Programming (Proceedings 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003)

A2 - Baeten, J.C.M.

A2 - Lenstra, J.K.

A2 - Parrow, J.

A2 - Woeginger, G.J.

PB - Springer

CY - Berlin

ER -

Sitters RA, Stougie L, Paepe, de WE. A competitive algorithm for the general 2-server problem. In Baeten JCM, Lenstra JK, Parrow J, Woeginger GJ, editors, Automata, Languages and Programming (Proceedings 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003). Berlin: Springer. 2003. p. 624-636. (Lecture Notes in Computer Science). https://doi.org/10.1007/3-540-45061-0_50