Document Open Access Logo

On the Facility Location Problem in Online and Dynamic Models

Authors Xiangyu Guo, Janardhan Kulkarni, Shi Li, Jiayi Xian

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.42.pdf
  • Filesize: 0.58 MB
  • 23 pages

Document Identifiers

Author Details

Xiangyu Guo
  • Department of Computer Science and Engineering, University at Buffalo, NY, USA
Janardhan Kulkarni
  • The Algorithms Group, Microsoft Research, Redmond, WA, USA
Shi Li
  • Department of Computer Science and Engineering, University at Buffalo, NY, USA
Jiayi Xian
  • Department of Computer Science and Engineering, University at Buffalo, NY, USA

Funding

X. Guo, S. Li and J. Xian are partially supported by NSF grants CCF- 1717134 and CCF-1844890.

Cite AsGet BibTex

Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian. On the Facility Location Problem in Online and Dynamic Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 42:1-42:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.42

Abstract

In this paper we study the facility location problem in the online with recourse and dynamic algorithm models. In the online with recourse model, clients arrive one by one and our algorithm needs to maintain good solutions at all time steps with only a few changes to the previously made decisions (called recourse). We show that the classic local search technique can lead to a (1+√2+ε)-competitive online algorithm for facility location with only O(log n/ε log 1/ε) amortized facility and client recourse, where n is the total number of clients arrived during the process. We then turn to the dynamic algorithm model for the problem, where the main goal is to design fast algorithms that maintain good solutions at all time steps. We show that the result for online facility location, combined with the randomized local search technique of Charikar and Guha [Charikar and Guha, 2005], leads to a (1+√2+ε)-approximation dynamic algorithm with total update time of Õ(n²) in the incremental setting against adaptive adversaries. The approximation factor of our algorithm matches the best offline analysis of the classic local search algorithm. Finally, we study the fully dynamic model for facility location, where clients can both arrive and depart. Our main result is an O(1)-approximation algorithm in this model with O(|F|) preprocessing time and O(nlog³ D) total update time for the HST metric spaces, where |F| is the number of potential facility locations. Using the seminal results of Bartal [Bartal, 1996] and Fakcharoenphol, Rao and Talwar [Fakcharoenphol et al., 2003], which show that any arbitrary N-point metric space can be embedded into a distribution over HSTs such that the expected distortion is at most O(log N), we obtain an O(log |F|) approximation with preprocessing time of O(|F|²log |F|) and O(nlog³ D) total update time. The approximation guarantee holds in expectation for every time step of the algorithm, and the result holds in the oblivious adversary model.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
  • Theory of computation → Online algorithms
Keywords
  • Facility location
  • online algorithm
  • recourse

Metrics

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

Related Versions

References

  1. Aris Anagnostopoulos, Russell Bent, Eli Upfal, and Pascal Van Hentenryck. A simple and deterministic competitive algorithm for online facility location. Inf. Comput., 194(2):175-202, November 2004. URL: https://doi.org/10.1016/j.ic.2004.06.002.
  2. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristic for k-median and facility location problems. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 21-29, 2001. URL: https://doi.org/10.1145/380752.380755.
  3. Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS '96, pages 184-, Washington, DC, USA, 1996. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=874062.875536.
  4. Yair Bartal, Avrim Blum, Carl Burch, and Andrew Tomkins. A polylog(n)-competitive algorithm for metrical task systems. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 711-719, 1997. URL: https://doi.org/10.1145/258533.258667.
  5. Guy E. Blelloch, Yan Gu, and Yihan Sun. Efficient construction of probabilistic tree embeddings. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 26:1-26:14, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.26.
  6. Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. k-server via multiscale entropic regularization. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 3-16, 2018. URL: https://doi.org/10.1145/3188745.3188798.
  7. T-H. Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dynamic k-center clustering. In Proceedings of the 2018 World Wide Web Conference, WWW ?18, page 579?587, Republic and Canton of Geneva, CHE, 2018. International World Wide Web Conferences Steering Committee. URL: https://doi.org/10.1145/3178876.3186124.
  8. Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for facility location problems. SIAM J. Comput., 34(4):803-824, April 2005. URL: https://doi.org/10.1137/S0097539701398594.
  9. Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 3250-3260, 2019. URL: http://papers.nips.cc/paper/8588-fully-dynamic-consistent-facility-location.
  10. Marek Cygan, Artur Czumaj, Marcin Mucha, and Piotr Sankowski. Online facility location with deletions. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pages 21:1-21:15, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.21.
  11. Yunus Esencayi, Marco Gaboardi, Shi Li, and Di Wang. Facility location problem in differential privacy model revisited. CoRR, abs/1910.12050, 2019. URL: http://arxiv.org/abs/1910.12050.
  12. Jittat Fakcharoenphol, Satish Rao, 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, STOC '03, pages 448-455, New York, NY, USA, 2003. ACM. URL: https://doi.org/10.1145/780542.780608.
  13. Dimitris Fotakis. Incremental algorithms for facility location and k-median. Theor. Comput. Sci., 361(2-3):275-313, 2006. URL: https://doi.org/10.1016/j.tcs.2006.05.015.
  14. Dimitris Fotakis. A primal-dual algorithm for online non-uniform facility location. J. of Discrete Algorithms, 5(1):141-148, March 2007. URL: https://doi.org/10.1016/j.jda.2006.03.001.
  15. Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1-57, 2008. URL: https://doi.org/10.1007/s00453-007-9049-y.
  16. Dimitris Fotakis. Memoryless facility location in one pass. ACM Trans. Algorithms, 7(4):49:1-49:24, 2011. URL: https://doi.org/10.1145/2000807.2000817.
  17. Dimitris Fotakis. Online and incremental algorithms for facility location. SIGACT News, 42(1):97-131, March 2011. URL: https://doi.org/10.1145/1959045.1959065.
  18. Monia Ghobadi, Ratul Mahajan, Amar Phanishayee, Nikhil R. Devanur, Janardhan Kulkarni, Gireeja Ranade, Pierre-Alexandre Blanche, Houman Rastegarfar, Madeleine Glick, and Daniel C. Kilper. Projector: Agile reconfigurable data center interconnect. In Proceedings of the ACM SIGCOMM 2016 Conference, Florianopolis, Brazil, August 22-26, 2016, pages 216-229, 2016. URL: https://doi.org/10.1145/2934872.2934911.
  19. Gramoz Goranci, Monika Henzinger, and Dariusz Leniowski. A tree structure for dynamic facility location. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pages 39:1-39:13, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.39.
  20. Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '98, pages 649-657, Philadelphia, PA, USA, 1998. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=314613.315037.
  21. Monika Henzinger, Dariusz Leniowski, and Claire Mathieu. Dynamic clustering to minimize the sum of radii. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 48:1-48:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.48.
  22. Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1975-1984. PMLR, 2017. URL: http://proceedings.mlr.press/v70/lattanzi17a.html.
  23. Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput., 222:45-58, 2013. Google Scholar
  24. A. Meyerson. Online facility location. In Proceedings of the 42Nd IEEE Symposium on Foundations of Computer Science, FOCS '01, pages 426-, Washington, DC, USA, 2001. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=874063.875567.
  25. Kamesh Munagala. Local search for k-medians and facility location. In Encyclopedia of Algorithms, pages 1139-1143. Springer, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_212.
  26. Seeun Umboh. Online network design algorithms via hierarchical decompositions. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1373-1387, 2015. URL: https://doi.org/10.1137/1.9781611973730.91.
  27. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, New York, NY, USA, 1st edition, 2011. 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 Imprint Privacy Contact