Complexity and approximation of the connected set-cover problem

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

doi:10.1007/s10898-011-9726-x

Complexity and approximation of the connected set-cover problem

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

Research output: Contribution to journal › Article › peer-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(log^2-ε n)-approximation for any ε > 0 for the connected set-cover problem on general graphs, unless NP has an quasi-polynomial Las-Vegas algorithm.

Original language	English
Pages (from-to)	563-572
Number of pages	10
Journal	Journal of Global Optimization
Volume	53
Issue number	3
DOIs	https://doi.org/10.1007/s10898-011-9726-x
Publication status	Published - 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

Access to Document

10.1007/s10898-011-9726-x

Cite this

@article{2e1733ceecab4fe5b11172dfdd608cd4,

title = "Complexity and approximation of the connected set-cover problem",

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.",

keywords = "Approximation algorithms, Computational complexity, Connected set-cover",

author = "Wei Zhang and Weili Wu and Wonjun Lee and Du, {Ding Zhu}",

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).",

year = "2012",

month = jul,

doi = "10.1007/s10898-011-9726-x",

language = "English",

volume = "53",

pages = "563--572",

journal = "Journal of Global Optimization",

issn = "0925-5001",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Complexity and approximation of the connected set-cover problem

AU - Zhang, Wei

AU - Wu, Weili

AU - Lee, Wonjun

AU - Du, Ding Zhu

N1 - 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).

PY - 2012/7

Y1 - 2012/7

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Computational complexity

KW - Connected set-cover

UR - http://www.scopus.com/inward/record.url?scp=84863723977&partnerID=8YFLogxK

U2 - 10.1007/s10898-011-9726-x

DO - 10.1007/s10898-011-9726-x

M3 - Article

AN - SCOPUS:84863723977

SN - 0925-5001

VL - 53

SP - 563

EP - 572

JO - Journal of Global Optimization

JF - Journal of Global Optimization

IS - 3

ER -

Complexity and approximation of the connected set-cover problem

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this