Problème de couverture maximale

En algorithmique, le problème de couverture maximale consiste à couvrir un nombre maximal d'éléments avec au plus k sous-ensembles mis à disposition.

Ce problème algorithmique est NP-dur et il existe des algorithmes d'approximation pour le résoudre. C'est une variante du problème de couverture par ensembles.

Définition

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.

Optimisation linéaire en nombre entier

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

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

Extensions

Citons deux extensions :

• Le problème de couverture maximale avec budget 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é 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.

Bibliographie

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