Dehghani, Sina ;
Ehsani, Soheil ;
Hajiaghayi, MohammadTaghi ;
Liaghat, Vahid ;
Seddighin, Saeed
Stochastic kServer: How Should Uber Work?
Abstract
In this paper we study a stochastic variant of the celebrated $k$server problem. In the kserver problem, we are required to minimize the total movement of k servers that are serving an online sequence of $t$ requests in a metric. In the stochastic setting we are given t independent distributions <P_1, P_2, ..., P_t> in advance, and at every time step i a request is drawn from P_i.
Designing the optimal online algorithm in such setting is NPhard, therefore the emphasis of our work is on designing an approximately optimal online algorithm. We first show a structural characterization for a certain class of nonadaptive online algorithms. We prove that in general metrics, the best of such algorithms has a cost of no worse than three times that of the optimal online algorithm. Next, we present an integer program that finds the optimal algorithm of this class for any arbitrary metric. Finally by rounding the solution of the linear relaxation of this program, we present an online algorithm for the stochastic kserver problem with an approximation factor of $3$ in the line and circle metrics and factor of O(log n) in general metrics. In this way, we achieve an approximation factor that is independent of k, the number of servers.
Moreover, we define the Uber problem, motivated by extraordinary growth of online network transportation services. In the Uber problem, each demand consists of two points a source and a destination in the metric. Serving a demand is to move a server to its source and then to its destination. The objective is again minimizing the total movement of the k given servers. It is not hard to show that given an alphaapproximation algorithm for the kserver problem, we can obtain a max{3,alpha}approximation algorithm for the Uber problem. Motivated by the fact that demands are usually highly correlated with the time (e.g. what day of the week or what time of the day the demand is arrived), we study the stochastic Uber problem. Using our results for stochastic kserver we can obtain a 3approximation algorithm for the stochastic Uber problem in line and circle metrics, and a O(log n)approximation algorithm for a general metric of size n.
Furthermore, we extend our results to the correlated setting where the probability of a request arriving at a certain point depends not only on the time step but also on the previously arrived requests.
BibTeX  Entry
@InProceedings{dehghani_et_al:LIPIcs:2017:7480,
author = {Sina Dehghani and Soheil Ehsani and MohammadTaghi Hajiaghayi and Vahid Liaghat and Saeed Seddighin},
title = {{Stochastic kServer: How Should Uber Workl}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {126:1126:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7480},
URN = {urn:nbn:de:0030drops74806},
doi = {10.4230/LIPIcs.ICALP.2017.126},
annote = {Keywords: kserver, stochastic, competitive ratio, online algorithm, Uber}
}
07.07.2017
Keywords: 

kserver, stochastic, competitive ratio, online algorithm, Uber 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 