Problème de couverture maximale

L'entrée du problème est un ensemble d'éléments, une liste de sous-ensembles de cet ensemble, et un entier k, et l'on doit trouver k sous-ensembles tels que le nombre d'éléments appartenant à au moins l'un de ceux-ci est maximisé. On dit qu'un élément est couvert s'il appartient à l'un des sous-ensembles sélectionnés.

On peut formaliser le problème comme un problème d'optimisation linéaire en nombre entier:

maximiser	${\displaystyle \sum _{e_{j}\in E}y_{j}}$	(maximiser le nombre d'élément couvert)
sous les contraintes	${\displaystyle \sum {x_{i}}\leq k}$	(au plus ${\displaystyle k}$ sous-ensembles sont sélectionnés)
	${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$	(si ${\displaystyle y_{j}>0}$ alors au moins un sous-ensemble ${\displaystyle e_{j}\in S_{i}}$ est selectionné)
	${\displaystyle y_{j}\in \{0,1\}}$	(si ${\displaystyle y_{j}=1}$ alors ${\displaystyle e_{j}}$ est couvert)
	${\displaystyle x_{i}\in \{0,1\}}$	(si ${\displaystyle x_{i}=1}$ alors ${\displaystyle S_{i}}$ sélectionné)

Citons deux extensions :

• Le problème de couverture maximale avec budget[3] consiste à attribuer un coût à chaque sous-ensemble. L'objectif est toujours de maximiser le nombre d'éléments couverts mais sans dépasser un budget alloué.
• Le problème de couverture maximale généralisé[4] consiste à attribuer un coût à chaque sous-ensemble, ainsi qu'un coût et un poids à chaque élément selon quel sous-ensemble le couvre.

• Vijay V. Vazirani, Approximation Algorithms, Springer-Verlag, 2001, 380 p. (ISBN 3-540-65367-8, lire en ligne)