A competitive algorithm for the general 2-server problem

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

doi:10.1007/3-540-45061-0_50

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 proceeding › Conference contribution › Academic › peer-review

12 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 language	English
Title of host publication	Automata, Languages and Programming (Proceedings 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003)
Editors	J.C.M. Baeten, J.K. Lenstra, J. Parrow, G.J. Woeginger
Place of Publication	Berlin
Publisher	Springer
Pages	624-636
ISBN (Print)	3-540-40493-7
DOIs	https://doi.org/10.1007/3-540-45061-0_50
Publication status	Published - 2003

Publication series

Name	Lecture Notes in Computer Science
Volume	2719
ISSN (Print)	0302-9743

Access to Document

10.1007/3-540-45061-0_50

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). 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)",

}

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 proceeding › Conference contribution › Academic › peer-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). doi: 10.1007/3-540-45061-0_50

A competitive algorithm for the general 2-server problem

Abstract

Publication series

Access to Document

Fingerprint

Cite this