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.

Advisors: 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