Further Stochastic Analysis of the k-Server Problem on the Circle

Jarett Schwartz

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2018-125
August 17, 2018

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-125.pdf

We consider a stochastic version of the k-server problem, analyzing the cost of the greedy algorithm on the circle. We fully characterize the distribution yielded by this process for k = 2. Next, we show new results for larger values of k. Then, we consider other variants of this process. Finally, we confirm the above results in simulations of the process.

Advisor: Alistair Sinclair


BibTeX citation:

@mastersthesis{Schwartz:EECS-2018-125,
    Author = {Schwartz, Jarett},
    Title = {Further Stochastic Analysis of the k-Server Problem on the Circle},
    School = {EECS Department, University of California, Berkeley},
    Year = {2018},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-125.html},
    Number = {UCB/EECS-2018-125},
    Abstract = {We consider a stochastic version of the k-server problem, analyzing the cost of the greedy algorithm on the circle. We fully characterize the distribution yielded by this process for k = 2. Next, we show new results for larger values of k. Then, we consider other variants of this process. Finally, we confirm the above results in simulations of the process.}
}

EndNote citation:

%0 Thesis
%A Schwartz, Jarett
%T Further Stochastic Analysis of the k-Server Problem on the Circle
%I EECS Department, University of California, Berkeley
%D 2018
%8 August 17
%@ UCB/EECS-2018-125
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-125.html
%F Schwartz:EECS-2018-125