Thumbnail

A note on the Clustered Set Covering Problem

Alfandari, Laurent; Monnot, Jérôme (2014), A note on the Clustered Set Covering Problem, Discrete Applied Mathematics, 164, p. 13--19. 10.1016/j.dam.2011.11.030

View/Open
Type
Article accepté pour publication ou publié
Date
2014
Journal name
Discrete Applied Mathematics
Volume
164
Publisher
Elsevier
Pages
13--19
Publication identifier
Metadata
Show full item record
Author(s)
Alfandari, Laurent
ESSEC Business School
Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We define an NP-hard clustered variant of the SetCoveringProblem where subsets are partitioned into K clusters and a fixed cost is paid for selecting at least one subset in a given cluster. 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 View the MathML source.
Subjects / Keywords
Setcovering; Maximal coverage; Approximation; Integer programming