Complexity and approximation of the connected set-cover problem

Wei Zhang, Weili Wu, Wonjun Lee, Ding Zhu Du

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

In this paper, we study the computational complexity and approximation complexity of the connected set-cover problem. We derive necessary and sufficient conditions for the connected set-cover problem to have a polynomial-time algorithm. We also present a sufficient condition for the existence of a (1 + ln δ)-approximation. In addition, one such (1 + ln δ)-approximation algorithm for this problem is proposed. Furthermore, it is proved that there is no polynomial-time O(log2-ε n)-approximation for any ε > 0 for the connected set-cover problem on general graphs, unless NP has an quasi-polynomial Las-Vegas algorithm.

Original languageEnglish
Pages (from-to)563-572
Number of pages10
JournalJournal of Global Optimization
Volume53
Issue number3
DOIs
Publication statusPublished - 2012 Jul

Bibliographical note

Funding Information:
Acknowledgments This work was supported in part by the National Scientific Foundation of USA under Grant No. CNS-0524429, CCF-0627233, and CCF-0514796 and also was jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), a NRF Grant under (KRF-2008-314-D00354), and MKE, Korea under ITRC NIPA-2010-(C1090-1021-0008).

Keywords

  • Approximation algorithms
  • Computational complexity
  • Connected set-cover

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Complexity and approximation of the connected set-cover problem'. Together they form a unique fingerprint.

Cite this