2026-08-17T18:56:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9811 2024-03-06T10:44:59Z ddc:004 open_access

Distributed Set Cover Approximation: Primal-Dual with Optimal Locality Even, Guy Ghaffari, Mohsen Medina, Moti Distributed Algorithms Approximation Algorithms Set Cover Vertex Cover 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guy Even and Mohsen Ghaffari and Moti Medina 2018 Is Part Of LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2018.22 urn:nbn:de:0030-drops-98114 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.22 eng https://creativecommons.org/licenses/by/3.0/legalcode