title: Problème de couverture maximale
text: # 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ément couvert) |
  | - | - | - |
  | 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 selectionné) |
  | | $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.
  