Document Open Access Logo

Nearly-Tight Lower Bounds for Set Cover and Network Design with Deadlines/Delay

Author Noam Touitou

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.53.pdf
  • Filesize: 0.74 MB
  • 16 pages

Document Identifiers

Author Details

Noam Touitou
  • Tel Aviv University, Israel

Cite As Get BibTex

Noam Touitou. Nearly-Tight Lower Bounds for Set Cover and Network Design with Deadlines/Delay. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.53

Abstract

In network design problems with deadlines/delay, an algorithm must make transmissions over time to satisfy connectivity requests on a graph. To satisfy a request, a transmission must be made that provides the desired connectivity. In the deadline case, this transmission must occur inside a time window associated with the request. In the delay case, the transmission should be as soon as possible after the request’s release, to avoid delay cost.
In FOCS 2020, frameworks were given which reduce a network design problem with deadlines/delay to its classic, offline variant, while incurring an additional competitiveness loss factor of O(log n), where n is the number of vertices in the graph. Trying to improve upon this loss factor is thus a natural research direction.
The frameworks of FOCS 2020 also apply to set cover with deadlines/delay, in which requests arrive on the elements of a universe over time, and the algorithm must transmit sets to serve them. In this problem, a universe of sets and elements is given, requests arrive on elements over time, and the algorithm must transmit sets to serve them.
In this paper, we give nearly tight lower bounds for set cover with deadlines/delay. These lower bounds imply nearly-tight lower bounds of Ω(log n / log log n) for a few network design problems, such as node-weighted Steiner forest and directed Steiner tree. Our results imply that the frameworks in FOCS 2020 are essentially optimal, and improve quadratically over the best previously-known lower bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Online algorithms
Keywords
  • Network Design
  • Deadlines
  • Delay
  • Online
  • Set Cover

Metrics

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

References

  1. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. A general approach to online network optimization problems. ACM Trans. Algorithms, 2(4):640-660, 2006. URL: https://doi.org/10.1145/1198513.1198522.
  2. 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 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, pages 1:1-1:20, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.1.
  3. Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou. Set cover with delay - clairvoyance is not required. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 8:1-8:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.8.
  4. Yossi Azar and Amit Jacob Fanani. Deterministic min-cost matching with delays. In Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers, pages 21-35, 2018. URL: https://doi.org/10.1007/978-3-030-04693-4_2.
  5. Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi. Online service with delay. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 551-563, 2017. URL: https://doi.org/10.1145/3055399.3055475.
  6. Yossi Azar, Runtian Ren, and Danny Vainstein. The min-cost matching with concave delays problem. CoRR, abs/2011.02017, 2020. URL: http://arxiv.org/abs/2011.02017.
  7. Yossi Azar and Noam Touitou. General framework for metric optimization problems with delay or with deadlines. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 60-71, 2019. URL: https://doi.org/10.1109/FOCS.2019.00013.
  8. Yossi Azar and Noam Touitou. Beyond tree embeddings - a deterministic framework for network design with deadlines or delay. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1368-1379. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00129.
  9. Piotr Berman and Chris Coulston. On-line algorithms for steiner tree problems (extended abstract). In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 344-353, New York, NY, USA, 1997. ACM. URL: https://doi.org/10.1145/258533.258618.
  10. Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Veselý. Online algorithms for multi-level aggregation. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 12:1-12:17, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.12.
  11. Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Dorian Nogneng, and Jirí Sgall. Better approximation bounds for the joint replenishment problem. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 42-54, 2014. URL: https://doi.org/10.1137/1.9781611973402.4.
  12. Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, and Pawel Schmidt. A primal-dual online deterministic algorithm for matching with delays. In Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers, pages 51-68, 2018. URL: https://doi.org/10.1007/978-3-030-04693-4_4.
  13. Marcin Bienkowski, Artur Kraska, and Pawel Schmidt. A match in time saves nine: Deterministic online matching with delays. In Approximation and Online Algorithms - 15th International Workshop, WAOA 2017, Vienna, Austria, September 7-8, 2017, Revised Selected Papers, pages 132-146, 2017. URL: https://doi.org/10.1007/978-3-319-89441-6_11.
  14. Marcin Bienkowski, Artur Kraska, and Pawel Schmidt. Online service with delay on a line. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers, pages 237-248, 2018. URL: https://doi.org/10.1007/978-3-030-01325-7_22.
  15. Carlos Fisch Brito, Elias Koutsoupias, and Shailesh Vaya. Competitive analysis of organization networks or multicast acknowledgment: How much to wait? Algorithmica, 64(4):584-605, 2012. URL: https://doi.org/10.1007/s00453-011-9567-5.
  16. Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Ohad Talmon. O(depth)-competitive algorithm for online multi-level aggregation. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1235-1244, 2017. URL: https://doi.org/10.1137/1.9781611974782.80.
  17. Niv Buchbinder, Kamal Jain, and Joseph Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, pages 253-264, 2007. URL: https://doi.org/10.1007/978-3-540-75520-3_24.
  18. Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, and Maxim Sviridenko. Online make-to-order joint replenishment model: primal dual competitive algorithms. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 952-961, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347186.
  19. Rodrigo A. Carrasco, Kirk Pruhs, Cliff Stein, and José Verschae. The online set aggregation problem. In LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, pages 245-259, 2018. URL: https://doi.org/10.1007/978-3-319-77404-6_19.
  20. Daniel R. Dooly, Sally A. Goldman, and Stephen D. Scott. TCP dynamic acknowledgment delay: Theory and practice (extended abstract). In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 389-398, 1998. URL: https://doi.org/10.1145/276698.276792.
  21. Yuval Emek, Shay Kutten, and Roger Wattenhofer. Online matching: haste makes waste! In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 333-344, 2016. URL: https://doi.org/10.1145/2897518.2897557.
  22. Yuval Emek, Yaacov Shapiro, and Yuyi Wang. Minimum cost perfect matching with delays for two sources. In Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, pages 209-221, 2017. URL: https://doi.org/10.1007/978-3-319-57586-5_18.
  23. 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.
  24. Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi. Online and stochastic survivable network design. SIAM J. Comput., 41(6):1649-1672, 2012. URL: https://doi.org/10.1137/09076725X.
  25. Anupam Gupta, Amit Kumar, and Debmalya Panigrahi. Caching with time windows. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1125-1138. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384277.
  26. Makoto Imase and Bernard M. Waxman. Dynamic steiner tree problem. SIAM J. Discrete Math., 4(3):369-384, 1991. URL: https://doi.org/10.1137/0404033.
  27. Anna R. Karlin, Claire Kenyon, and Dana Randall. Dynamic TCP acknowledgment and other stories about e/(e-1). Algorithmica, 36(3):209-224, 2003. Google Scholar
  28. Simon Korman. On the use of randomization in the online set cover problem. Master’s thesis, Weizmann Institute of Science, 2005. Google Scholar
  29. J. Naor, D. Panigrahi, and M. Singh. Online node-weighted steiner tree and related problems. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 210-219, 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 About DROPS Imprint Privacy Contact