Problème de couverture par ensembles

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, le problème de couverture par ensembles (Set Cover problem en anglais[1]) est un problème d'algorithmique particulièrement important.

Étant donné un ensemble A, on dit qu'un élément e est couvert par A si e appartient à A. Étant donné un ensemble U et une famille S de sous-ensembles de U, le problème consiste à couvrir tous les éléments U avec une sous-famille de S la plus petite possible.

Une version plus générale consiste à assigner des poids aux éléments de S, et à chercher la sous-famille de poids minimal.

Exemple introductif[modifier | modifier le code]

On considère un ensemble de cinq éléments à couvrir : U=\{1,2,3,4,5 \}. On considère les sous-ensembles : \{1,2\}, \{3,4\}, \{4,5\} et \{1,2,3\}. On essaye de couvrir tous les éléments avec des sous-ensembles. Par exemple \{1,2\}, \{3,4\}, \{4,5\} est une couverture, puisque chaque élément est dans au moins un des sous-ensembles. La couverture qui utilise le moins de sous-ensemble est \{4,5\},\{1,2,3\}, c'est donc cette couverture que l'on cherche à calculer.

Définition formelle[modifier | modifier le code]

Le problème de décision est le suivant :

Entrée : un entier k, un ensemble U fini et S un sous-ensemble de l'ensemble des parties de U
Question : existe-il un sous-ensemble T de S, de taille inférieur à k, tel que l'union des éléments présents dans les sous-ensembles de T est égal à U ?

Le problème d'optimisation associé consiste à minimiser le nombre de sous-ensembles utilisés.

Dans une forme plus générale du problème, à chaque ensemble S on associe un poids c(S), et le but est de minimiser la somme des poids de la couverture.

Propriétés algorithmiques et complexité[modifier | modifier le code]

NP-complétude[modifier | modifier le code]

Le problème de couverture par ensembles est NP-difficile (et NP-complet dans sa forme décisionnelle). C'est l'un des 21 problèmes NP-complets de Karp (Karp 1972). Une des preuves classiques est une réduction du problème de couverture par sommets.

Formulation sous forme de programme linéaire[modifier | modifier le code]

Il est fructueux d'exprimer ce problème comme un problème d'optimisation linéaire en nombres entier.

En prenant une variable x_S pour chaque sous-ensemble, le programme linéaire naturel est le suivant :

minimiser : \sum_{S \in \mathcal S}x_S (Minimiser le nombre de sous-ensembles)
tel que : \sum_{S\colon e \in S} x_S \geqslant 1 \forall e\in \mathcal U (Tous les éléments sont couverts)
x_S \in \{0,1\} \forall S\in \mathcal S. (Chaque sous-ensemble est, ou bien dans la couverture, ou bien pas)

Si l'on associe un poids c(S) à chaque ensemble, le problème devient :

minimiser : \sum_{S \in \mathcal S}c(S) \cdot x_S (Minimiser le poids total des sous-ensembles)
tel que : \sum_{S\colon e \in S} x_S \geqslant 1 \forall e\in \mathcal U (Tous les éléments sont couverts)
x_S \in \{0,1\} \forall S\in \mathcal S. (Chaque sous-ensemble est, ou bien dans la couverture, ou bien pas)

Relations avec d'autres problèmes algorithmiques[modifier | modifier le code]

Algorithmes d'approximation[modifier | modifier le code]

Le problème de couverture par ensemble étant NP-complet, de nombreux algorithmes d'approximation ont été inventés. On peut citer en exemple l'algorithme glouton, un algorithme de dual fitting, un algorithme par arrondi à partir du programme linéaire, et un schéma primal-dual[2].

Il existe des résultats sur la difficulté d'approximation du problème, dûs d'abord à Lund (en) et Yannakakis[3] puis Feige (en)[4], puis Raz (en), Safra, Alon et Moshkovitz. Ce dernier résultat donne une borne inférieure de c\cdot\ln{n}, où c est une constante, sous l'hypothèse P différent de NP[5],[6]. Ces résultats sont basés sur les preuves interactives et le théorème PCP[7].

Importance du problème et historique[modifier | modifier le code]

Vijay Vazirani dit dans son livre (Vazirani 2001), que «l'étude de ce problème a permis le developpement de techniques qui ont ensuite été utilisées dans tout le domaine [des algorithmes d'approximation]»[8].

Bibliographie[modifier | modifier le code]

  • (en) Václav Chvátal, « A Greedy Heuristic for the Set-Covering Problem. », Mathematics of Operations Research, vol. 4, no 3,‎ 1979, p. 233-235
  • Ran Raz et Shmuel Safra, « A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP », dans STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, ACM,‎ 1997 (ISBN 978-0-89791-888-6), p. 475-484.

Notes et références[modifier | modifier le code]

  1. cette traduction française est notamment présente dans la traduction de (Vazirani 2001) (voir la table des matière sur le site de Nicolas Schabanel (traducteur))
  2. (en) Vijay Vazirani, Approximation algorithms, Springer Verlag,‎ 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 2, 13, 14 et 15.
  3. Lund et Yannakakis 1994
  4. Feige 1998
  5. Raz et Safra 1997
  6. Alon, Moshkovitz et Safra 2006
  7. Voir par exemple l'introduction de l'article de Lund et Yannakakis.
  8. En anglais : a problem whose study led to the development of fundamental techniques for the entire field.