We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Complexity and approximation of the connected set-cover problem.
- Authors
Zhang, Wei; Wu, Weili; Lee, Wonjun; Du, Ding-Zhu
- 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-\varepsilon} n)}$$ -approximation for any $${\varepsilon\,{>}\,0}$$ for the connected set-cover problem on general graphs, unless NP has an quasi-polynomial Las-Vegas algorithm.
- Subjects
COMPUTATIONAL complexity; APPROXIMATION algorithms; POLYNOMIAL approximation; APPROXIMATION theory; LOGARITHMS; GRAPHIC methods
- Publication
Journal of Global Optimization, 2012, Vol 53, Issue 3, p563
- ISSN
0925-5001
- Publication type
Article
- DOI
10.1007/s10898-011-9726-x