Problème de couverture maximale
From Wikipedia, the free encyclopedia
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[1],[2]. C'est une variante du problème de couverture par ensembles.
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é) |
