Even, Guy ;
Ghaffari, Mohsen ;
Medina, Moti
Distributed Set Cover Approximation: PrimalDual with Optimal Locality
Abstract
This paper presents a deterministic distributed algorithm for computing an f(1+epsilon) approximation of the wellstudied 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 fapproximation guarantee of standard centralized primaldual algorithms, which is known to be essentially the best possible approximation for polynomialtime 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 timeoptimal 2(1+epsilon)approximation of vertex cover, with round complexity O(log Delta/log log Delta), as presented by BarYehuda, CensorHillel, and Schwartzman [PODC'17] for weighted vertex cover. Our method is quite different and it can be viewed as a localityoptimal way of performing primaldual for the more general case of set cover. We note that the vertex cover algorithm of BarYehuda 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: PrimalDual with Optimal Locality}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {22:122:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770927},
ISSN = {18688969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9811},
URN = {urn:nbn:de:0030drops98114},
doi = {10.4230/LIPIcs.DISC.2018.22},
annote = {Keywords: Distributed Algorithms, Approximation Algorithms, Set Cover, Vertex Cover}
}
2018
Keywords: 

Distributed Algorithms, Approximation Algorithms, Set Cover, Vertex Cover 
Seminar: 

32nd International Symposium on Distributed Computing (DISC 2018)

Issue date: 

2018 
Date of publication: 

2018 