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 (maximiser le nombre d'éléments couverts) sous les contraintes (au plus sous-ensembles sont sélectionnés) (si alors au moins un sous-ensemble est sélectionné) (si alors est couvert) (si alors 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
Références
Catégorie:Problème NP-complet