Document Open Access Logo

Online Facility Location with Linear Delay

Authors Marcin Bienkowski , Martin Böhm , Jarosław Byrka , Jan Marcinkowski

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.45.pdf
  • Filesize: 0.85 MB
  • 17 pages

Document Identifiers

Author Details

Marcin Bienkowski
  • Institute of Computer Science, University of Wrocław, Poland
Martin Böhm
  • Institute of Computer Science, University of Wrocław, Poland
Jarosław Byrka
  • Institute of Computer Science, University of Wrocław, Poland
Jan Marcinkowski
  • Institute of Computer Science, University of Wrocław, Poland

Funding

  • Bienkowski, Marcin: Supported by Polish National Science Centre grant 2016/22/E/ ST6/00499.
  • Byrka, Jarosław: Supported by Polish National Science Centre grant 2020/39/B/ST6/01641.

Cite As Get BibTex

Marcin Bienkowski, Martin Böhm, Jarosław Byrka, and Jan Marcinkowski. Online Facility Location with Linear Delay. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 45:1-45:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.45

Abstract

In the problem of online facility location with delay, a sequence of n clients appear in the metric space, and they need to be eventually connected to some open facility. The clients do not have to be connected immediately, but such a choice comes with a certain penalty: each client incurs a waiting cost (equal to the difference between its arrival and its connection time). At any point in time, an algorithm may decide to open a facility and connect any subset of clients to it. That is, an algorithm needs to balance three types of costs: cost of opening facilities, costs of connecting clients, and the waiting costs of clients. We study a natural variant of this problem, where clients may be connected also to an already open facility, but such action incurs an extra cost: an algorithm pays for waiting of the facility (a cost incurred separately for each such "late" connection). This is reminiscent of online matching with delays, where both sides of the connection incur a waiting cost. We call this variant two-sided delay to differentiate it from the previously studied one-sided delay, where clients may connect to a facility only at its opening time.
We present an O(1)-competitive deterministic algorithm for the two-sided delay variant. Our approach is an extension of the approach used by Jain, Mahdian and Saberi [STOC 2002] for analyzing the performance of offline algorithms for facility location. To this end, we substantially simplify the part of the original argument in which a bound on the sequence of factor-revealing LPs is derived. We then show how to transform our O(1)-competitive algorithm for the two-sided delay variant to O(log n / log log n)-competitive deterministic algorithm for one-sided delays. This improves the known O(log n) bound by Azar and Touitou [FOCS 2020]. We note that all previous online algorithms for problems with delays in general metrics have at least logarithmic ratios.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • online facility location
  • network design problems
  • facility location with delay
  • JMS algorithm
  • competitive analysis
  • factor revealing LP

Metrics

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

Supplementary Materials

References

  1. Karen Aardal, Jaroslaw Byrka, and Mohammad Mahdian. Facility location. In Encyclopedia of Algorithms, pages 717-724. Springer, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_139.
  2. Aris Anagnostopoulos, Russell Bent, Eli Upfal, and Pascal Van Hentenryck. A simple and deterministic competitive algorithm for online facility location. Information and Computation, 194(2):175-202, 2004. URL: https://doi.org/10.1016/j.ic.2004.06.002.
  3. Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul M. Makhijani, Yuyi Wang, and Roger Wattenhofer. Min-cost bipartite perfect matching with delays. In Proc. 20th Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 1:1-1:20, 2017. Google Scholar
  4. Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays. In Proc. 28th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 1051-1061, 2017. Google Scholar
  5. Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou. Set cover with delay - clairvoyance is not required. In Proc. 28th European Symp. on Algorithms (ESA), pages 8:1-8:21, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.8.
  6. Yossi Azar and Amit Jacob Fanani. Deterministic min-cost matching with delays. Theory of Computing Systems, 64(4):572-592, 2020. URL: https://doi.org/10.1007/s00224-019-09963-7.
  7. Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi. Online service with delay. In Proc. 49th ACM Symp. on Theory of Computing (STOC), pages 551-563, 2017. Google Scholar
  8. Yossi Azar, Runtian Ren, and Danny Vainstein. The min-cost matching with concave delays problem. In Proc. 2021 ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 301-320, 2021. URL: https://doi.org/10.1137/1.9781611976465.20.
  9. Yossi Azar and Noam Touitou. General framework for metric optimization problems with delay or with deadlines. In Proc. 60th IEEE Symp. on Foundations of Computer Science (FOCS), pages 60-71, 2019. URL: https://doi.org/10.1109/FOCS.2019.00013.
  10. Yossi Azar and Noam Touitou. Beyond tree embeddings - a deterministic framework for network design with deadlines or delay. In Proc. 61st IEEE Symp. on Foundations of Computer Science (FOCS), pages 1368-1379, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00129.
  11. Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Lukasz Jez, Jirí Sgall, Nguyen Kim Thang, and Pavel Veselý. Online algorithms for multilevel aggregation. Operations Research, 68(1):214-232, 2020. URL: https://doi.org/10.1287/opre.2019.1847.
  12. Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Lukasz Jez, Jirí Sgall, Nguyen Kim Thang, and Pavel Veselý. New results on multi-level aggregation. Theoretical Computer Science, 861:133-143, 2021. URL: https://doi.org/10.1016/j.tcs.2021.02.016.
  13. Marcin Bienkowski, Martin Böhm, Jarosław Byrka, and Jan Marcinkowski. Data and computations for online facility location with linear delay. https://github.com/bohm/fl-double-sided-waiting, 2021.
  14. Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż, Dorian Nogneng, and Jirí Sgall. Better approximation bounds for the joint replenishment problem. In Proc. 25th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 42-54, 2014. Google Scholar
  15. Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż, Jiři Sgall, and Grzegorz Stachowiak. Online control message aggregation in chain networks. In Proc. 13th Int. Workshop on Algorithms and Data Structures (WADS), pages 133-145, 2013. Google Scholar
  16. Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, and Pawel Schmidt. A primal-dual online deterministic algorithm for matching with delays. In Proc. 16th Workshop on Approximation and Online Algorithms (WAOA), pages 51-68, 2018. URL: https://doi.org/10.1007/978-3-030-04693-4_4.
  17. Marcin Bienkowski, Artur Kraska, and Paweł Schmidt. A match in time saves nine: Deterministic online matching with delays. In Proc. 15th Workshop on Approximation and Online Algorithms (WAOA), pages 132-146, 2017. Google Scholar
  18. Marcin Bienkowski, Artur Kraska, and Paweł Schmidt. Online service with delay on a line. In Proc. 25th Int. Colloq. on Structural Information and Communication Complexity (SIROCCO), pages 237-248, 2018. URL: https://doi.org/10.1007/978-3-030-01325-7_22.
  19. Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Ohad Talmon. O(depth)-competitive algorithm for online multi-level aggregation. In Proc. 28th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 1235-1244, 2017. Google Scholar
  20. Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, and Maxim Sviridenko. Online make-to-order joint replenishment model: Primal-dual competitive algorithms. Operations Research, 61(4):1014-1029, 2013. URL: https://doi.org/10.1287/opre.2013.1188.
  21. Jaroslaw Byrka and Karen Aardal. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM Journal on Computing, 39(6):2212-2231, 2010. URL: https://doi.org/10.1137/070708901.
  22. Rodrigo A. Carrasco, Kirk Pruhs, Cliff Stein, and José Verschae. The online set aggregation problem. In Proc. 13th Latin American Theoretical Informatics Symposium (LATIN), pages 245-259, 2018. URL: https://doi.org/10.1007/978-3-319-77404-6_19.
  23. Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for facility location problems. SIAM Journal on Computing, 34(4):803-824, 2005. URL: https://doi.org/10.1137/S0097539701398594.
  24. Marek Chrobak. Online aggregation problems. SIGACT News, 45(1):91-102, 2014. Google Scholar
  25. Fabián A. Chudak and David B. Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. SIAM Journal on Computing, 33(1):1-25, 2003. URL: https://doi.org/10.1137/S0097539703405754.
  26. Daniel R. Dooly, Sally A. Goldman, and Stephen D. Scott. On-line analysis of the TCP acknowledgment delay problem. Journal of the ACM, 48(2):243-273, 2001. Google Scholar
  27. Yuval Emek, Shay Kutten, and Roger Wattenhofer. Online matching: haste makes waste! In Proc. 48th ACM Symp. on Theory of Computing (STOC), pages 333-344, 2016. Google Scholar
  28. Yuval Emek, Yaacov Shapiro, and Yuyi Wang. Minimum cost perfect matching with delays for two sources. Theoretical Computer Science, 754:122-129, 2019. URL: https://doi.org/10.1016/j.tcs.2018.07.004.
  29. Dimitris Fotakis. A primal-dual algorithm for online non-uniform facility location. Journal of Discrete Algorithms, 5(1):141-148, 2007. URL: https://doi.org/10.1016/j.jda.2006.03.001.
  30. 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.
  31. Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31(1):228-248, 1999. URL: https://doi.org/10.1006/jagm.1998.0993.
  32. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL: https://www.gurobi.com.
  33. Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay V. Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Journal of the ACM, 50(6):795-824, 2003. URL: https://doi.org/10.1145/950620.950621.
  34. Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In Proc. 34th ACM Symp. on Theory of Computing (STOC), pages 731-740, 2002. URL: https://doi.org/10.1145/509907.510012.
  35. Anna R. Karlin, Claire Kenyon, and Dana Randall. Dynamic TCP acknowledgement and other stories about e/(e - 1). Algorithmica, 36(3):209-224, 2003. Google Scholar
  36. Madhukar R. Korupolu, C. Greg Plaxton, and Rajmohan Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37(1):146-188, 2000. URL: https://doi.org/10.1006/jagm.2000.1100.
  37. Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45-58, 2013. URL: https://doi.org/10.1016/j.ic.2012.01.007.
  38. Xingwu Liu, Zhida Pan, Yuyi Wang, and Roger Wattenhofer. Impatient online matching. In Proc. 29th Int. Symp. on Algorithms and Computation (ISAAC), pages 62:1-62:12, 2018. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.62.
  39. Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang. Approximation algorithms for metric facility location problems. SIAM Journal on Computing, 36(2):411-432, 2006. URL: https://doi.org/10.1137/S0097539703435716.
  40. Adam Meyerson. Online facility location. In Proc. 42nd IEEE Symp. on Foundations of Computer Science (FOCS), pages 426-431, 2001. URL: https://doi.org/10.1109/SFCS.2001.959917.
  41. David B. Shmoys, Éva Tardos, and Karen Aardal. Approximation algorithms for facility location problems (extended abstract). In Proc. 29th ACM Symp. on Theory of Computing (STOC), pages 265-274, 1997. URL: https://doi.org/10.1145/258533.258600.
  42. Michael A. Stanko and David H. Henard. How crowdfunding influences innovation. MIT Sloan Management Review, 57(3):15, 2016. 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