Thumbnail - Request a copy

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

Type
Communication / Conférence
Date
2010
Conference title
ISCO International Symposium on Combinatorial Optimization
Conference date
2010-03
Conference city
Hammamet
Conference country
Tunisie
Journal name
Electronic Notes in Discrete Mathematics
Volume
36
Publisher
Elsevier
Pages
479-485
Publication identifier
Metadata
Show full item record
Author(s)
Alfandari, Laurent
Monnot, Jérôme cc
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 / Keywords
Approximation; NP-hardness; Maximal Coverage; Set Covering; Integer Programming