Geodesic
Stochastic Analysis of the $k$-Server Problem on the Circle
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2010_special_258_a27,
     author = {Anagnostopoulos, Aris and Dombry, Cl\'ement and Guillotin-Plantard, Nadine and Kontoyiannis, Ioannis and Upfal, Eli},
     title = {Stochastic {Analysis} of the $k${-Server} {Problem} on the {Circle}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)},
     year = {2010},
     doi = {10.46298/dmtcs.2791},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2791/}
}
TY  - JOUR
AU  - Anagnostopoulos, Aris
AU  - Dombry, Clément
AU  - Guillotin-Plantard, Nadine
AU  - Kontoyiannis, Ioannis
AU  - Upfal, Eli
TI  - Stochastic Analysis of the $k$-Server Problem on the Circle
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2791/
DO  - 10.46298/dmtcs.2791
LA  - en
ID  - DMTCS_2010_special_258_a27
ER  - 
%0 Journal Article
%A Anagnostopoulos, Aris
%A Dombry, Clément
%A Guillotin-Plantard, Nadine
%A Kontoyiannis, Ioannis
%A Upfal, Eli
%T Stochastic Analysis of the $k$-Server Problem on the Circle
%J Discrete mathematics & theoretical computer science
%D 2010
%V DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2791/
%R 10.46298/dmtcs.2791
%G en
%F DMTCS_2010_special_258_a27
Anagnostopoulos, Aris; Dombry, Clément; Guillotin-Plantard, Nadine; Kontoyiannis, Ioannis; Upfal, Eli. Stochastic Analysis of the $k$-Server Problem on the Circle. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010). doi : 10.46298/dmtcs.2791. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2791/

Cité par Sources :