Document Open Access Logo

Distributed Set Cover Approximation: Primal-Dual with Optimal Locality

Authors Guy Even, Mohsen Ghaffari, Moti Medina

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.22.pdf
  • Filesize: 481 kB
  • 14 pages

Document Identifiers

Author Details

Guy Even
  • Tel-Aviv University, Israel
Mohsen Ghaffari
  • ETH Zurich, Switzerland
Moti Medina
  • Ben-Gurion University, Israel

Cite AsGet BibTex

Guy Even, Mohsen Ghaffari, and Moti Medina. Distributed Set Cover Approximation: Primal-Dual with Optimal Locality. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.22

Abstract

This paper presents a deterministic distributed algorithm for computing an f(1+epsilon) approximation of the well-studied minimum set cover problem, for any constant epsilon>0, in O(log (f Delta)/log log (f Delta)) rounds. Here, f denotes the maximum element frequency and Delta denotes the cardinality of the largest set. This f(1+epsilon) approximation almost matches the f-approximation guarantee of standard centralized primal-dual algorithms, which is known to be essentially the best possible approximation for polynomial-time computations. The round complexity almost matches the Omega(log (Delta)/log log (Delta)) lower bound of Kuhn, Moscibroda, Wattenhofer [JACM'16], which holds for even f=2 and for any poly(log Delta) approximation. Our algorithm also gives an alternative way to reproduce the time-optimal 2(1+epsilon)-approximation of vertex cover, with round complexity O(log Delta/log log Delta), as presented by Bar-Yehuda, Censor-Hillel, and Schwartzman [PODC'17] for weighted vertex cover. Our method is quite different and it can be viewed as a locality-optimal way of performing primal-dual for the more general case of set cover. We note that the vertex cover algorithm of Bar-Yehuda et al. does not extend to set cover (when f >= 3).

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed Algorithms
  • Approximation Algorithms
  • Set Cover
  • Vertex Cover

Metrics

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

References

  1. Matti Åstrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures, pages 294-302. ACM, 2010. Google Scholar
  2. Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. Distributed approximation of maximum independent set and maximum matching. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 165-174, 2017. URL: http://dx.doi.org/10.1145/3087801.3087806.
  3. Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A Distributed (2+ε)-Approximation for Vertex Cover in O(log Δ/ ε log logΔ) Rounds. J. ACM, 64(3):23:1-23:11, 2017. URL: http://dx.doi.org/10.1145/3060294.
  4. Reuven Bar-Yehuda and Shimon Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2(2):198-203, 1981. Google Scholar
  5. Reuven Bar-Yehuda and Shimon Even. A local-ratio theorem for approximating the weighted vertex cover problem. Technion-Israel Institute of Technology. Department of Computer Science, 1983. Google Scholar
  6. Reuven Bar-Yehuda and Dror Rawitz. On the equivalence between the primal-dual schema and the local ratio technique. SIAM Journal on Discrete Mathematics, 19(3):762-797, 2005. Google Scholar
  7. R. Ben-Basat, G. Even, K. Kawarabayashi, and G. Schwartzman. A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(log nlogΔ / log²logΔ) Rounds. ArXiv e-prints (Appeared in SIROCCO 2018), 2018. URL: http://arxiv.org/abs/1804.01308.
  8. Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev. A new multilayered pcp and the hardness of hypergraph vertex cover. SIAM Journal on Computing, 34(5):1129-1146, 2005. Google Scholar
  9. Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of mathematics, pages 439-485, 2005. Google Scholar
  10. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. Google Scholar
  11. Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 270-277, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch20.
  12. Mohsen Ghaffari, David G Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. arXiv preprint arXiv:1711.02194, 2017. Google Scholar
  13. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 784-797. ACM, 2017. Google Scholar
  14. Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798-859, 2001. Google Scholar
  15. Jonas Holmerin. Improved inapproximability results for vertex cover on k-uniform hypergraphs. In International Colloquium on Automata, Languages, and Programming, pages 1005-1016. Springer, 2002. Google Scholar
  16. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. Journal of Computer and System Sciences, 74(3):335-349, 2008. Google Scholar
  17. Christos Koufogiannakis and Neal E Young. Distributed algorithms for covering, packing and maximum weighted matching. Distributed Computing, 24(1):45-63, 2011. Google Scholar
  18. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. The price of being near-sighted. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 980-989. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  19. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. J. ACM, 63(2):17:1-17:44, 2016. URL: http://dx.doi.org/10.1145/2742012.
  20. Nathan Linial. Distributive graph algorithms global solutions from local data. In Foundations of Computer Science, 1987., 28th Annual Symposium on, pages 331-335. IEEE, 1987. Google Scholar
  21. Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM (JACM), 41(5):960-981, 1994. Google Scholar
  22. Dana Moshkovitz. The projection games conjecture and the np-hardness of ln n-approximating set-cover. Theory of Computing, 11:221-235, 2015. URL: http://dx.doi.org/10.4086/toc.2015.v011a007.
  23. David Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000. Google Scholar
  24. Jukka Suomela. Survey of local algorithms. ACM Computing Surveys (CSUR), 45(2):24, 2013. Google Scholar
  25. Luca Trevisan. Non-approximability results for optimization problems on bounded degree instances. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 453-461. ACM, 2001. Google Scholar
  26. Vijay V Vazirani. Approximation algorithms. Springer Science &Business Media, 2013. Google Scholar
  27. David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 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 Imprint Privacy Contact