License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.22
URN: urn:nbn:de:0030-drops-98114
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9811/
Even, Guy ;
Ghaffari, Mohsen ;
Medina, Moti
Distributed Set Cover Approximation: Primal-Dual with Optimal Locality
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).
BibTeX - Entry
@InProceedings{even_et_al:LIPIcs:2018:9811,
author = {Guy Even and Mohsen Ghaffari and Moti Medina},
title = {{Distributed Set Cover Approximation: Primal-Dual with Optimal Locality}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {22:1--22:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-092-7},
ISSN = {1868-8969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9811},
URN = {urn:nbn:de:0030-drops-98114},
doi = {10.4230/LIPIcs.DISC.2018.22},
annote = {Keywords: Distributed Algorithms, Approximation Algorithms, Set Cover, Vertex Cover}
}
Keywords: |
|
Distributed Algorithms, Approximation Algorithms, Set Cover, Vertex Cover |
Collection: |
|
32nd International Symposium on Distributed Computing (DISC 2018) |
Issue Date: |
|
2018 |
Date of publication: |
|
04.10.2018 |