Abstract
This paper studies the online \(k\)-server problem with max-distance objective, i.e. minimizing the maximum distance moved among all the servers. For this objective, we prove that no deterministic online algorithm has a competitive ratio better than \(k\). We also analyze several classical algorithms for two special cases and show that some algorithms do have a competitive ratio of \(k\) and hence optimal. Consequently, we conjecture that any metric space allows for a deterministic \(k\)-competitive \(k\)-server algorithm with max-distance objective.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bartal Y, Koutsoupias E (2004) On the competitive ratio of the work function algorithm for the \(k\)-server problem. Theor Comput Sci 324:337–345
Bein WW, Chrobak M, Larmore LL (2002) The 3-server problem in the plane. Theor Comput Sci 289: 335–354
Borodin A, EI-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge
Chrobak M, Larmore LL (1991) An optimal on-line algorithm for \(k\) severs on trees. SIAM J Comput 20:144–148
Chrobak M, Larmore LL (1992) The server problem and on-line games. DIMAGS Ser Discrete Math Theor Comput Sci 7:11–64
Chrobak M, Karloff J, Payne TH, Vishwanathan S (1991) New results on server problems. SIAM J Discrete Math 4:172–181
Kleinberg MJ (1990) A lower bound for two-server balancing algorithms. Inf Process Lett 52:39–43
Koutsoupias E (2009) The \(k\)-server problem. Comput Sci Rev 3:105–118
Koutsoupias E, Papadimitriou C (1994) On the \(k\)-server conjecture. In: Proceedings of the 26th Symposium on Theory of Computing, STOC, ACM, pp 507–511
Koutsoupias E, Papadimitriou C (1996) The 2-evader problem. Inf Process Lett 57:249–252
Lipmann M (2003) Online routing. Technische Universiteit Eindhoven, Eindhoven
Manasse SM, McGeoch AL, Sleator DD (1990) Competitive algorithms for server problems. J Algorithms 11:208–230
Sleator DD, Tarjan ER (1985) Amortized efficiency of list update and paging rules. Commun ACM 28: 202–208
Vinvenzo B, Leen S (2009) Online \(k\)-server routing problems. Theory Comput Syst 45:470–485
Acknowledgments
This work is supported by National Natural Science Foundation of China under Grants 71071123, 61221063, 71172197 and 71131006 and Program for Changjiang Scholars and Innovative Research Team in University under Grant IRT1173 and Central University Fund of Sichuan University under Grant skgt201202.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Xu, Y., Li, H., He, C. et al. The online \(k\)-server problem with max-distance objective. J Comb Optim 29, 836–846 (2015). https://doi.org/10.1007/s10878-013-9621-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-013-9621-0