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/
Go to the corresponding LIPIcs Volume Portal

Even, Guy ; Ghaffari, Mohsen ; Medina, Moti

Distributed Set Cover Approximation: Primal-Dual with Optimal Locality

pdf-format:
LIPIcs-DISC-2018-22.pdf (0.5 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI