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.FSTTCS.2013.249
URN: urn:nbn:de:0030-drops-43775
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4377/
Go to the corresponding LIPIcs Volume Portal

Agarwal, Archita ; Chakaravarthy, Venkatesan T. ; Choudhury, Anamitra Roy ; Roy, Sambuddha ; Sabharwal, Yogish

Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers

pdf-format:
18.pdf (0.5 MB)

Abstract

In this paper, we study a class of set cover problems that satisfy a special property which we call the small neighborhood cover property.
This class encompasses several well-studied problems including vertex cover, interval cover, bag interval cover and tree cover. We design unified distributed and parallel algorithms that can handle any set cover problem falling under the above framework and yield constant factor approximations. These algorithms run in polylogarithmic communication rounds in the distributed setting and are in NC, in the parallel setting.

BibTeX - Entry

@InProceedings{agarwal_et_al:LIPIcs:2013:4377,
  author =	{Archita Agarwal and Venkatesan T. Chakaravarthy and Anamitra Roy Choudhury and Sambuddha Roy and Yogish Sabharwal},
  title =	{{Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{249--261},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4377},
  URN =		{urn:nbn:de:0030-drops-43775},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.249},
  annote =	{Keywords: approximation algorithms, set cover problem, tree cover}
}

Keywords: approximation algorithms, set cover problem, tree cover
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

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