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
Titre du colloque
ISCO International Symposium on Combinatorial Optimization
Date du colloque
2010-03
Ville du colloque
Hammamet
Pays du colloque
Tunisie
Nom de la revue
Electronic Notes in Discrete Mathematics
Volume
36
Éditeur
Elsevier
Pages
479-485
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Alfandari, Laurent
Monnot, Jérôme cc
Résumé (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 .
Mots-clés
Approximation; NP-hardness; Maximal Coverage; Set Covering; Integer Programming