License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.53
URN: urn:nbn:de:0030-drops-154865
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15486/
Touitou, Noam
Nearly-Tight Lower Bounds for Set Cover and Network Design with Deadlines/Delay
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.
BibTeX - Entry
@InProceedings{touitou:LIPIcs.ISAAC.2021.53,
author = {Touitou, Noam},
title = {{Nearly-Tight Lower Bounds for Set Cover and Network Design with Deadlines/Delay}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {53:1--53:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15486},
URN = {urn:nbn:de:0030-drops-154865},
doi = {10.4230/LIPIcs.ISAAC.2021.53},
annote = {Keywords: Network Design, Deadlines, Delay, Online, Set Cover}
}
|
Keywords: |
|
Network Design, Deadlines, Delay, Online, Set Cover |
|
Collection: |
|
32nd International Symposium on Algorithms and Computation (ISAAC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.11.2021 |
