2026-07-23T10:25:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15486 2024-03-06T10:55:25Z ddc:004 open_access

Nearly-Tight Lower Bounds for Set Cover and Network Design with Deadlines/Delay Touitou, Noam Network Design Deadlines Delay Online Set Cover 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noam Touitou 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.53 urn:nbn:de:0030-drops-154865 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.53 eng https://creativecommons.org/licenses/by/4.0/legalcode