Complexity and approximation of the connected set-cover problem

被引：6

作者：

Zhang, Wei ^{[1
]}

Wu, Weili ^{[2
]}

Lee, Wonjun ^{[3
]}

Du, Ding-Zhu ^{[2
,4
]}

机构：

[1] Xi An Jiao Tong Univ, Dept Appl Math, Xian 710049, Shaanxi, Peoples R China

[2] Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75083 USA

[3] Korea Univ, Dept Comp Sci & Engn, Seoul 136713, South Korea

[4] Korea Univ, WCU FNOT Res Ctr, Seoul, South Korea

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2012年 / 53卷 / 03期

基金：

美国国家科学基金会;

关键词：

Connected set-cover; Computational complexity; Approximation algorithms;

D O I：

10.1007/s10898-011-9726-x

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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 delta)-approximation. In addition, one such (1 + ln delta)-approximation algorithm for this problem is proposed. Furthermore, it is proved that there is no polynomial-time -approximation for any for the connected set-cover problem on general graphs, unless NP has an quasi-polynomial Las-Vegas algorithm.

引用

页码：563 / 572

页数：10