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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Shuai, T., Hu, X.: Connected set-cover problem and its applications. In: Proceeding of AAIM, pp. 243–254 (2006)
Gupta, H., Das, S., Gu, Q.: Connected sensor cover: self-organization of sensor networks for efficient query execution. In: Proceeding of ACM MOBIHOC (2003). doi:10.1145/778415.778438
Feige, U.: A threshold of ln n for approximating set-cover. In: Proceeding of ACM STOC (1998). doi:10.1145/285055.285059
Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. (1979). doi:10.2307/3689577
Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceeding of ACM STOC (2003). doi:10.1145/780542.780628
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhang, W., Wu, W., Lee, W. et al. Complexity and approximation of the connected set-cover problem. J Glob Optim 53, 563–572 (2012). https://doi.org/10.1007/s10898-011-9726-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-011-9726-x