TY - GEN
T1 - A competitive 3-server algorithm
AU - Berman, P.
AU - Karloff, H.
AU - Tardos, G.
N1 - Funding Information:
problem ch-competitive if for all metric spxes A:/, for all request sequences in M, the cost incllrred by our online algorithm on that request sequence is at most ck times the optimal cost of serving tha.t request sequence. Thus, for an online algorithm t.o be ck-competitive, the cost it incurs on a request sequence must not exceed ck times the minin~um ofline cost, the cost incurred by a prescient adversary with his own k servers and unlimited c.oni- l Pennsylvania State University, University Park, PA 16802. Research supported in part by AFOSR contract 87-0400 and NSF grant CR 8805978. # Department of Computer Science, University of Chicago, Chicago, IL 60637. Research supported in part by NSF grant CCR 8807534. l * E6tv6s University, Mlizeum krt 6-8, Budapest, Hungary H-1088. This work was partially done while the author visited University of Chicago, Chicago, IL 60637; DIMACS, Rutgers University, New Brunswick, NJ, 08903; and AT&T BelI Labs, Murray Hill, NJ 07974.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 1990/1/1
Y1 - 1990/1/1
N2 - The k-server problem is the problem of scheduling the motion of k mobile servers so as to serve a sequence of requests, where to serve a request is to move one of the k servers to the request site. Each request is served before any future requests are known. An online algorithm is known as competitive if its cost never exceeds a constant times that of an optimal offline adversary. Though no competitive deterministic online algorithms are known for any k > 2, we prove that a simple, natural randomized algorithm is competitive for the 3-server problem.
AB - The k-server problem is the problem of scheduling the motion of k mobile servers so as to serve a sequence of requests, where to serve a request is to move one of the k servers to the request site. Each request is served before any future requests are known. An online algorithm is known as competitive if its cost never exceeds a constant times that of an optimal offline adversary. Though no competitive deterministic online algorithms are known for any k > 2, we prove that a simple, natural randomized algorithm is competitive for the 3-server problem.
UR - http://www.scopus.com/inward/record.url?scp=84976668845&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84976668845&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84976668845
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 280
EP - 290
BT - Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990
PB - Association for Computing Machinery
T2 - 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990
Y2 - 22 January 1990 through 24 January 1990
ER -