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ésoudreModèle:,. 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\le k$	(au plus $k$ sous-ensembles sont sélectionnés)
	$\sum _{e_j\in S_i}{x}_i\ge 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

• Modèle:Ouvrage