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

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



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2013.249.pdf
  • Filesize: 476 kB
  • 13 pages

Document Identifiers

Author Details

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

Cite AsGet BibTex

Archita Agarwal, Venkatesan T. Chakaravarthy, Anamitra Roy Choudhury, Sambuddha Roy, and Yogish Sabharwal. Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 249-261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.FSTTCS.2013.249

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.
Keywords
  • approximation algorithms
  • set cover problem
  • tree cover

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail