Retour aux résultats
Actes d'une conférence (2010), Electronic Notes in Discrete Mathematics, ISCO

Approximation of the Clustered Set Covering Problem

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 multi-commodity flow problems in transportation planning.

ALFANDARI, L. and MONNOT, J. (2010). Approximation of the Clustered Set Covering Problem. In: Electronic Notes in Discrete Mathematics. ISCO.