Optimal Distributed Covering Algorithms

Authors Ran Ben-Basat , Guy Even , Ken-ichi Kawarabayashi , Gregory Schwartzman



PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.5.pdf
  • Filesize: 0.62 MB
  • 15 pages

Document Identifiers

Author Details

Ran Ben-Basat
  • Harvard University, Cambridge, MA, United States
Guy Even
  • Tel Aviv University, Tel Aviv, Israel
Ken-ichi Kawarabayashi
  • National Institute of Informatics, Tokyo, Japan
Gregory Schwartzman
  • National Institute of Informatics, Tokyo, Japan

Acknowledgements

We thank the anonymous reviewers for their helpful remarks.

Cite AsGet BibTex

Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Optimal Distributed Covering Algorithms. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.DISC.2019.5

Abstract

We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f. The approximation factor of our algorithm is (f+epsilon). Let Delta denote the maximum degree in the hypergraph. Our algorithm runs in the congest model and requires O(log{Delta} / log log Delta) rounds, for constants epsilon in (0,1] and f in N^+. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal distributed algorithms. For constant values of f and epsilon, our algorithm improves over the (f+epsilon)-approximation algorithm of [Fabian Kuhn et al., 2006] whose running time is O(log Delta + log W), where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f-approximation for the problem in O(f log n) rounds, improving over the classical result of [Samir Khuller et al., 1994] that achieves a running time of O(f log^2 n). Finally, for weighted vertex cover (f=2) our algorithm achieves a deterministic running time of O(log n), matching the randomized previously best result of [Koufogiannakis and Young, 2011]. We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an (f+epsilon)-approximate integral solution in O((1+f/log n)* ((log Delta)/(log log Delta) + (f * log M)^{1.01}* log epsilon^{-1}* (log Delta)^{0.01})) rounds, where f bounds the number of variables in a constraint, Delta bounds the number of constraints a variable appears in, and M=max {1, ceil[1/a_{min}]}, where a_{min} is the smallest normalized constraint coefficient. This improves over the results of [Fabian Kuhn et al., 2006] for the integral case, which combined with rounding achieves the same guarantees in O(epsilon^{-4}* f^4 * log f * log(M * Delta)) rounds.

Subject Classification

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

Metrics

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

References

  1. Matti Astrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. A Local 2-Approximation Algorithm for the Vertex Cover Problem. In DISC, 2009. Google Scholar
  2. Matti Astrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In SPAA, 2010. Google Scholar
  3. Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. Distributed Approximation of Maximum Independent Set and Maximum Matching. In PODC. ACM, 2017. Google Scholar
  4. Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds. J. ACM, 2017. Google Scholar
  5. R. Ben-Basat, G. Even, K.-i. Kawarabayashi, and G. Schwartzman. A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(log nlogΔ / log²logΔ) Rounds. In SIROCCO, 2018. Google Scholar
  6. R. Ben-Basat, K.-i. Kawarabayashi, and G. Schwartzman. Distributed Set Cover Approximation: Primal-Dual with Optimal Locality. In DISC, 2019. Google Scholar
  7. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. In FOCS, 2016. Google Scholar
  8. Richard Cole and Uzi Vishkin. Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Information and Control, 1986. Google Scholar
  9. Guy Even, Mohsen Ghaffari, and Moti Medina. Distributed Set Cover Approximation: Primal-Dual with Optimal Locality. In DISC, 2018. Google Scholar
  10. Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In SODA. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  11. Mohsen Ghaffari and Hsin-Hao Su. Distributed Degree Splitting, Edge Coloring, and Orientations. In SODA, 2017. Google Scholar
  12. Fabrizio Grandoni, Jochen Könemann, and Alessandro Panconesi. Distributed weighted vertex cover via maximal matchings. ACM Transactions on Algorithms, 2008. URL: https://doi.org/10.1145/1435375.1435381.
  13. Dorit S. Hochbaum. Approximation Algorithms for the Set Covering and Vertex Cover Problems. SIAM J. Comput., 1982. Google Scholar
  14. Richard M. Karp. Reducibility Among Combinatorial Problems. In Proceedings of a symposium on the Complexity of Computer Computations, 1972. Google Scholar
  15. Samir Khuller, Uzi Vishkin, and Neal E. Young. A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers. J. Algorithms, 1994. Google Scholar
  16. Christos Koufogiannakis and Neal E. Young. Distributed algorithms for covering, packing and maximum weighted matching. Distributed Computing, 2011. Google Scholar
  17. Fabian Kuhn. The price of locality: exploring the complexity of distributed coordination primitives. PhD thesis, ETH Zurich, 2005. Google Scholar
  18. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. The price of being near-sighted. In SODA, 2006. Google Scholar
  19. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local Computation: Lower and Upper Bounds. J. ACM, 2016. Google Scholar
  20. Alessandro Panconesi and Romeo Rizzi. Some simple distributed algorithms for sparse networks. Distributed Computing, 2001. Google Scholar
  21. Valentin Polishchuk and Jukka Suomela. A simple local 3-approximation algorithm for vertex cover. Inf. Process. Lett., 2009. 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