Document Open Access Logo

Stochastic k-Server: How Should Uber Work?

Authors Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, Saeed Seddighin

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.126.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Sina Dehghani
Soheil Ehsani
MohammadTaghi Hajiaghayi
Vahid Liaghat
Saeed Seddighin

Cite As Get BibTex

Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Saeed Seddighin. Stochastic k-Server: How Should Uber Work?. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 126:1-126:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.126

Abstract

In this paper we study a stochastic variant of the celebrated $k$-server problem. In the k-server 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 NP-hard, 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 non-adaptive 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 k-server 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 alpha-approximation algorithm for the k-server 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 k-server we can obtain a 3-approximation 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.

Subject Classification

Keywords
  • k-server
  • stochastic
  • competitive ratio
  • online algorithm
  • Uber

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Melika Abolhasani, Soheil Ehsani, Hosein Esfandiari, MohammadTaghi Hajiaghayi, Robert Kleinberg, and Brendan Lucier. Beating 1-1/e for ordered prophets. arXiv preprint arXiv:1704.05836, 2017. Google Scholar
  2. Dimitris Achlioptas, Marek Chrobak, and John Noga. Competitive analysis of randomized paging algorithms. Theoretical Computer Science, 234(1):203-218, 2000. Google Scholar
  3. Saeed Alaei, Mohammad T Hajiaghayi, Vahid Liaghat, Dan Pei, and Barna Saha. Adcell: Ad allocation in cellular networks. In Algorithms-ESA 2011, pages 311-322. Springer, 2011. Google Scholar
  4. Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. Online prophet-inequality matching with applications to ad allocation. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 18-35. ACM, 2012. Google Scholar
  5. Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. The online stochastic generalized assignment problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 11-25. Springer, 2013. Google Scholar
  6. Susanne Albers, Lene M Favrholdt, and Oliver Giel. On paging with locality of reference. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 258-267. ACM, 2002. Google Scholar
  7. Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A polylogarithmic-competitive algorithm for the k-server problem. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 267-276. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.63.
  8. Nikhil Bansal, Niv Buchbinder, and Joseph Seffi Naor. A primal-dual randomized algorithm for weighted paging. Journal of the ACM (JACM), 59(4):19, 2012. Google Scholar
  9. Yair Bartal, Marek Chrobak, and Lawrence L Larmore. A randomized algorithm for two servers on the line. Information and Computation, 158(1):53-69, 2000. Google Scholar
  10. Yair Bartal and Elias Koutsoupias. On the competitive ratio of the work function algorithm for the k-server problem. Theoretical computer science, 324(2):337-345, 2004. Google Scholar
  11. Luca Becchetti. Modeling locality: A probabilistic analysis of lru and fwf. In Algorithms-ESA 2004, pages 98-109. Springer, 2004. Google Scholar
  12. Avrim Blum, Carl Burch, and Adam Kalai. Finely-competitive paging. In Foundations of Computer Science, 1999. 40th Annual Symposium on, 1999. Google Scholar
  13. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. cambridge university press, 2005. Google Scholar
  14. Allan Borodin, Sandy Irani, Prabhakar Raghavan, and Baruch Schieber. Competitive paging with locality of reference. Journal of Computer and System Sciences, 50(2):244-258, 1995. Google Scholar
  15. Marek Chrobak, H Karloff, T Payne, and S Vishwnathan. New ressults on server problems. SIAM Journal on Discrete Mathematics, 4(2):172-181, 1991. Google Scholar
  16. Marek Chrobak and Lawrence L Larmore. An optimal on-line algorithm for k servers on trees. SIAM Journal on Computing, 20(1):144-148, 1991. Google Scholar
  17. Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Saeed Seddighin. Online survivable network design and prophets. 2015. Google Scholar
  18. Sina Dehghani, Ian A Kash, and Peter Key. Online stochastic scheduling and pricing the clouds. 2017. Google Scholar
  19. Peter J Denning. The working set model for program behavior. Communications of the ACM, 26(1):43-48, 1983. Google Scholar
  20. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 448-455. ACM, 2003. Google Scholar
  21. Amos Fiat, Richard M Karp, Michael Luby, Lyle A McGeoch, Daniel D Sleator, and Neal E Young. Competitive paging algorithms. Journal of Algorithms, 12(4):685-699, 1991. Google Scholar
  22. Amos Fiat and Manor Mendel. Truly online paging with locality of reference. In Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on, pages 326-335. IEEE, 1997. Google Scholar
  23. Amos Fiat and Manor Mendel. Better algorithms for unfair metrical task systems and applications. SIAM Journal on Computing, 32(6):1403-1422, 2003. Google Scholar
  24. Naveen Garg, Anupam Gupta, Stefano Leonardi, and Piotr Sankowski. Stochastic analyses for online combinatorial optimization problems. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 942-951. Society for Industrial and Applied Mathematics, 2008. Google Scholar
  25. Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In AAAI, volume 7, pages 58-65, 2007. Google Scholar
  26. Sandy Irani, Anna R Karlin, and Steven Phillips. Strongly competitive algorithms for paging with locality of reference. SIAM Journal on Computing, 25(3):477-497, 1996. Google Scholar
  27. Anna R Karlin, Steven J Phillips, and Prabhakar Raghavan. Markov paging. SIAM Journal on Computing, 30(3):906-922, 2000. Google Scholar
  28. Howard Karloff, Yuval Rabani, and Yiftach Ravid. Lower bounds for randomized k-server and motion-planning algorithms. SIAM Journal on Computing, 23(2):293-312, 1994. Google Scholar
  29. Elias Koutsoupias and Christos H Papadimitriou. On the k-server conjecture. Journal of the ACM (JACM), 42(5):971-983, 1995. Google Scholar
  30. Ulrich Krengel, Louis Sucheston, et al. Semiamarts and finite values. Bull. Amer. Math. Soc, 83(4), 1977. Google Scholar
  31. Mark S Manasse, Lyle A McGeoch, and Daniel D Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11(2):208-230, 1990. Google Scholar
  32. Lyle A McGeoch and Daniel D Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6(1-6):816-825, 1991. Google Scholar
  33. Konstantinos Panagiotou and Alexander Souza. On adequate performance measures for paging. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 487-496. ACM, 2006. Google Scholar
  34. Daniel D Sleator and Robert E Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, 1985. Google Scholar
  35. Duru Türkoglu. The k-server problem and fractional analysis, 2005. Master’s Thesis, The University of Chicago. URL: http://people.cs.uchicago.edu/~duru/papers/masters.pdf.
  36. Neal E Young. Bounding the diffuse adversary. In SODA, volume 98, pages 420-425, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact