A competitive algorithm for the general 2-server problem

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

10 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
TitelAutomata, Languages and Programming (Proceedings 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003)
RedacteurenJ.C.M. Baeten, J.K. Lenstra, J. Parrow, G.J. Woeginger
Plaats van productieBerlin
UitgeverijSpringer
Pagina's624-636
ISBN van geprinte versie3-540-40493-7
DOI's
StatusGepubliceerd - 2003

Publicatie series

NaamLecture Notes in Computer Science
Volume2719
ISSN van geprinte versie0302-9743

    Vingerafdruk

Citeer dit

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 (editors), Automata, Languages and Programming (Proceedings 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003) (blz. 624-636). (Lecture Notes in Computer Science; Vol. 2719). Berlin: Springer. https://doi.org/10.1007/3-540-45061-0_50