Document Open Access Logo

Set Cover with Delay - Clairvoyance Is Not Required

Authors Yossi Azar, Ashish Chiplunkar, Shay Kutten, Noam Touitou

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.8.pdf
  • Filesize: 0.58 MB
  • 21 pages

Document Identifiers

Author Details

Yossi Azar
  • Tel Aviv University, Israel
Ashish Chiplunkar
  • Indian Institute of Technology Delhi, India
Shay Kutten
  • Technion - Israel Institute of Technology, Haifa, Israel
Noam Touitou
  • Tel Aviv University

Funding

  • Azar, Yossi: Supported in part by the Israel Science Foundation (grant No. 1506/16).
  • Chiplunkar, Ashish: Supported by Pankaj Gupta Young Faculty fellowship.
  • Kutten, Shay: Supported by the Ministry of Science and Technology together with the JSPS, as well as the BSF.

Cite As Get BibTex

Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou. Set Cover with Delay - Clairvoyance Is Not Required. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.8

Abstract

In most online problems with delay, clairvoyance (i.e. knowing the future delay of a request upon its arrival) is required for polylogarithmic competitiveness. In this paper, we show that this is not the case for set cover with delay (SCD) - specifically, we present the first non-clairvoyant algorithm, which is O(log n log m)-competitive, where n is the number of elements and m is the number of sets. This matches the best known result for the classic online set cover (a special case of non-clairvoyant SCD). Moreover, clairvoyance does not allow for significant improvement - we present lower bounds of Ω(√{log n}) and Ω(√{log m}) for SCD which apply for the clairvoyant case. 
In addition, the competitiveness of our algorithm does not depend on the number of requests. Such a guarantee on the size of the universe alone was not previously known even for the clairvoyant case - the only previously-known algorithm (due to Carrasco et al.) is clairvoyant, with competitiveness that grows with the number of requests. 
For the special case of vertex cover with delay, we show a simpler, deterministic algorithm which is 3-competitive (and also non-clairvoyant).

Subject Classification

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

Metrics

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

Related Versions

References

  1. Sebastian Abshoff, Christine Markarian, and Friedhelm Meyer auf der Heide. Randomized online algorithms for set cover leasing problems. In 8th COCOA, pages 25-34, 2014. Google Scholar
  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 Proceedings of the APPROX/RANDOM, pages 1:1-1:20, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.1.
  3. Baruch Awerbuch, Yossi Azar, Amos Fiat, and Frank Thomson Leighton. Making commitments in the face of uncertainty: How to pick a winner almost every time. In Proceedings of the Twenty-Eighth STOC, pages 519-530, 1996. URL: https://doi.org/10.1145/237814.238000.
  4. Y. Azar and A. Jacob-Fanani. Deterministic Min-Cost Matching with Delays. ArXiv e-prints, June 2018. URL: http://arxiv.org/abs/1806.03708.
  5. Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays. In 28th SODA, pages 1051-1061, 2017. URL: https://doi.org/10.1137/1.9781611974782.67.
  6. Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi. Online service with delay. In 49th STOC, pages 551-563, 2017. URL: https://doi.org/10.1145/3055399.3055475.
  7. Yossi Azar and Noam Touitou. General framework for metric optimization problems with delay or with deadlines. In Proceedings of the 60th IEEE FOCS, pages 60-71, 2019. URL: https://doi.org/10.1109/FOCS.2019.00013.
  8. Nikhil Bansal and Ho-Leung Chan. Weighted flow time does not admit o(1)-competitive algorithms. In Proceedings of the Twentieth SODA, pages 1238-1244, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496904.
  9. Kshipra Bhawalkar, Sreenivas Gollapudi, and Debmalya Panigrahi. Online set cover with set requests. In Proceedings of the APPROX/RANDOM, pages 64-79, 2014. Google Scholar
  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 Proceedings of the 24th ESA, pages 12:1-12:17, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.12.
  11. Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, and Pawel Schmidt. A primal-dual online deterministic algorithm for matching with delays. CoRR, abs/1804.08097, 2018. URL: http://arxiv.org/abs/1804.08097.
  12. Marcin Bienkowski, Artur Kraska, and Pawel Schmidt. A match in time saves nine: Deterministic online matching with delays. In 15th WAOA, pages 132-146, 2017. URL: https://doi.org/10.1007/978-3-319-89441-6_11.
  13. Marcin Bienkowski, Artur Kraska, and Pawel Schmidt. Online service with delay on a line. In 24th SIROCCO, 2018. Google Scholar
  14. Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Ohad Talmon. O(depth)-competitive algorithm for online multi-level aggregation. In Twenty-Eighth SODA, pages 1235-1244, 2017. URL: https://doi.org/10.1137/1.9781611974782.80.
  15. Rodrigo A. Carrasco, Kirk Pruhs, Cliff Stein, and José Verschae. The online set aggregation problem. In Proceedings of the LATIN 2018:, pages 245-259, 2018. URL: https://doi.org/10.1007/978-3-319-77404-6_19.
  16. Amit Chakrabarti and Anthony Wirth. Incidence geometries and the pass complexity of semi-streaming set cover. In Proceedings of the Twenty-Seventh SODA, pages 1365-1373, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch94.
  17. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624-633. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591884.
  18. Stefan Dobrev, Jeff Edmonds, Dennis Komm, Rastislav Královic, Richard Královic, Sacha Krug, and Tobias Mömke. Improved analysis of the online set cover problem with advice. Theor. Comput. Sci., 689:96-107, 2017. Google Scholar
  19. Daniel R. Dooly, Sally A. Goldman, and Stephen D. Scott. TCP dynamic acknowledgment delay: Theory and practice. In Proceedings of the Thirtieth STOC, pages 389-398, 1998. URL: https://doi.org/10.1145/276698.276792.
  20. Yuval Emek, Shay Kutten, and Roger Wattenhofer. Online matching: haste makes waste! In Proceedings of the 48th STOC, pages 333-344, 2016. URL: https://doi.org/10.1145/2897518.2897557.
  21. Yuval Emek and Adi Rosén. Semi-streaming set cover - (extended abstract). In Proceedings of the 41st ICALP, pages 453-464, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_38.
  22. Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh. Set covering with our eyes closed. SIAM J. Comput., 42(3):808-830, 2013. Google Scholar
  23. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. In Proceedings of the 49th STOC, pages 537-550, 2017. URL: https://doi.org/10.1145/3055399.3055493.
  24. Sungjin Im, Viswanath Nagarajan, and Ruben van der Zwaan. Minimum latency submodular cover. ACM Trans. Algorithms, 13(1):13:1-13:28, 2016. URL: https://doi.org/10.1145/2987751.
  25. Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, and Ravi Sundaram. Universal approximations for tsp, steiner tree, and set cover. In 37th STOC, pages 386-395, 2005. URL: https://doi.org/10.1145/1060590.1060649.
  26. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.019.
  27. Simon Korman. On the use of randomization in the online set cover problem. Master’s thesis, Weizmann Institute of Science, 2005. Google Scholar
  28. Noam Nisan. The communication complexity of approximate set packing and covering. In Proceedings of the ICALP, pages 868-875, 2002. URL: https://doi.org/10.1007/3-540-45465-9_74.
  29. Ashwin Pananjady, Vivek Kumar Bagaria, and Rahul Vaze. The online disjoint set cover problem and its applications. In 2015 IEEE INFOCOM, pages 1221-1229, 2015. Google Scholar
  30. Thomas W. Reiland. Optimality conditions and duality in continuous programming ii. the linear problem revisited. Journal of Mathematical Analysis and Applications, 1980. 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