Problème de couverture par ensembles

Exemple d'une instance du problème de couverture par ensembles.

En informatique théorique, le problème de couverture par ensembles (Set Cover problem en anglais) est un problème d'algorithmique particulièrement important car c'est l'un des 21 problèmes NP-complets de Karp Modèle:Harv.

É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

On considère un ensemble de cinq éléments à couvrir : $U=\{1,2,3,4,5\}$. On considère les sous-ensembles : $\{2,4\},\{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\},\{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-ensembles est $\{4,5\},\{1,2,3\}$, c'est donc cette couverture que l'on cherche à calculer.

Définition formelle

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érieure à $k$, tel que l'union des éléments présents dans les sous-ensembles de $T$ est égale à $U$ ?

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

Le problème se généralise à une version pondérée : à chaque ensemble $s\in 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é

NP-complétude

Le problème de couverture par ensembles est NP-difficile (et NP-complet dans sa forme décisionnelle). Une des preuves classiques est une réduction du problème de couverture par sommets.

Formulation sous forme de programme linéaire

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

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

minimiser :	$\sum _{S\in 𝒮}{x}_S$		(Minimiser le nombre de sous-ensembles)
tel que :	$\sum _{S:e\in S}{x}_S⩾1$	$\mathrm{\forall }e\in 𝒰$	(Tous les éléments sont couverts)
	$x_S\in \{0,1\}$	$\mathrm{\forall }S\in 𝒮$.	(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 𝒮}c(S)\cdot x_S$		(Minimiser le poids total des sous-ensembles)
tel que :	$\sum _{S:e\in S}{x}_S⩾1$	$\mathrm{\forall }e\in 𝒰$	(Tous les éléments sont couverts)
	$x_S\in \{0,1\}$	$\mathrm{\forall }S\in 𝒮$.	(Chaque sous-ensemble est, ou bien dans la couverture, ou bien pas)

Relations avec d'autres problèmes algorithmiques

• Le problème de couverture de sommets est un cas particulier de ce problème, sur un graphe.
• Le problème dual du problème de couverture par ensembles est le set packing.
• Le problème de la couverture exacte est le même problème mais avec une contrainte supplémentaire : les éléments de l'univers ne doivent être couverts qu'une seule fois.
• Le problème de couverture maximale est le même problème mais avec une contrainte supplémentaire : les éléments de l'univers ne doivent être couverts qu'un nombre maximal de fois.

Algorithmes

Algorithmes d'approximation

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. On peut analyser l'algorithme glouton avec la méthode des poids multiplicatifs. Le gap d'intégralité du LP est logarithmique.

Il existe des résultats sur la difficulté d'approximation du problème, dus d'abord à Lund et Yannakakis puis Feige, puis Raz, 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 NPModèle:,. Ces résultats sont basés sur les preuves interactives et le théorème PCP.

Algorithmes heuristiques

Des techniques pour résoudre les problèmes de couverture comprennent les méthodes exactes, la programmation mathématique, et des méthodes heuristiques et métaheuristiques, les algorithmes génétiques ou mémétiques. Parmi ces méthodes, certains algorithmes métaheuristiques peuvent résoudre des cas volumineux du problème de couverture en un temps raisonnable. Leurs hybridations avec d'autres techniques donnent des résultats encore meilleurs, tant dans les applications de référence que dans le monde réelModèle:,.

Importance du problème et historique

Ce problème d'optimisation combinatoire peut être lié à un large éventail d'applications du monde réel, par exemple la programmation des équipes, la localisation d'installations , les problèmes de logistique urbaine et le placement optimal des camérasModèle:,

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

Bibliographie

• Modèle:Approximation algorithms (Vazirani)
• Modèle:Reducibility Karp 1972
• Modèle:Article
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Article