Complexity and approximation of the connected set-cover problem

DOI10.1007/s10898-011-9726-xzbMath1250.90104OpenAlexW2099799577MaRDI QIDQ453623

Wei Zhang, Weili Wu, Ding-Zhu Du, Won Jun Lee

Publication date: 27 September 2012

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-011-9726-x

zbMATH Keywords

computational complexityapproximation algorithmsconnected set-cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

Multi-start iterated tabu search for the minimum weight vertex cover problem ⋮ Approximability results for the converse connectedp-centre problem^† ⋮ Approximation algorithms for the connected sensor cover problem

Cites Work

• A threshold of ln n for approximating set cover
• Polylogarithmic inapproximability
• A Greedy Heuristic for the Set-Covering Problem
• Connected Set Cover Problem and Its Applications

This page was built for publication: Complexity and approximation of the connected set-cover problem