Aris Anagnostopoulos ; Clément Dombry ; Nadine Guillotin-Plantard ; Ioannis Kontoyiannis ; Eli Upfal - Stochastic Analysis of the $k$-Server Problem on the Circle

dmtcs:2791 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2791
Stochastic Analysis of the $k$-Server Problem on the CircleArticle

Authors: Aris Anagnostopoulos 1; Clément Dombry 2; Nadine Guillotin-Plantard 3; Ioannis Kontoyiannis 4; Eli Upfal 5

  • 1 Department of Informatics and System Sciences
  • 2 Laboratoire de Mathématiques et Applications
  • 3 Institut Camille Jordan
  • 4 Department of Informatics [Athens]
  • 5 Department of Computer Science

We consider a stochastic version of the $k$-server problem in which $k$ servers move on a circle to satisfy stochastically generated requests. The requests are independent and identically distributed according to an arbitrary distribution on a circle, which is either discrete or continuous. The cost of serving a request is the distance that a server needs to move to reach the request. The goal is to minimize the steady-state expected cost induced by the requests. We study the performance of a greedy strategy, focusing, in particular, on its convergence properties and the interplay between the discrete and continuous versions of the process.


Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: $k$-server,probabilistic analysis,on-line algorithms,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

1 Document citing this article

Consultation statistics

This page has been seen 203 times.
This article's PDF has been downloaded 249 times.