Approximation of the Clustered Set Covering Problem
Alfandari, Laurent; Monnot, Jérôme (2010), Approximation of the Clustered Set Covering Problem, ISCO International Symposium on Combinatorial Optimization, 2010-03, Hammamet, Tunisie
TypeCommunication / Conférence
Conference titleISCO International Symposium on Combinatorial Optimization
Journal nameElectronic Notes in Discrete Mathematics
MetadataShow full item record
Abstract (EN)We define a NP-hard clustered variant of the Set Covering Problem where subsets are partitioned into K clusters and a fixed cost is paid for selecting at least one subset in a given cluster. This variant can reformulate as a master problem various multicommodity flow problems in transportation planning. We show that the problem is approximable within ratio (1 + ǫ)(e/e− 1)H(q), where q is the maximum number of elements covered by a cluster and H(q) = Pq i=1 1 i .
Subjects / KeywordsApproximation; NP-hardness; Maximal Coverage; Set Covering; Integer Programming
Showing items related by title and author.