Problème de couverture par ensembles

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

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

Entrée : un entier ${\displaystyle k}$, un ensemble ${\displaystyle U}$ fini et ${\displaystyle S}$ un sous-ensemble de l'ensemble des parties de ${\displaystyle U}$

Question : existe-il un sous-ensemble ${\displaystyle T}$ de ${\displaystyle S}$, de taille inférieure à ${\displaystyle k}$, tel que l'union des éléments présents dans les sous-ensembles de ${\displaystyle T}$ est égal à ${\displaystyle 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 ${\displaystyle S}$ on associe un poids ${\displaystyle c(S)}$, et le but est de minimiser la somme des poids de la couverture.

Ce problème d'optimisation combinatoire peut être lié à un large éventail d'applications du monde réel, par exemple la programmation des équipes[11], la localisation d'installations[12] , les problèmes de logistique urbaine[13] et le placement optimal des caméras[14] - [9]

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]»[15].

• (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7)
• (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103
• (en) Václav Chvátal, « A Greedy Heuristic for the Set-Covering Problem. », Mathematics of Operations Research, vol. 4, n^o 3,‎ 1979, p. 233-235
• Noga Alon, Dana Moshkovitz et Shmuel Safra, « Algorithmic construction of sets for k-restrictions », ACM Trans. Algorithms, ACM, vol. 2, n^o 2,‎ 2006, p. 153-177 (ISSN 1549-6325, DOI 10.1145/1150334.1150336).
• Uriel Feige, « A threshold of ln n for approximating set cover », Journal of the ACM, vol. 45, n^o 4,‎ 1998, p. 634-652 (ISSN 0004-5411, DOI 10.1145/285055.285059).
• Carsten Lund et Mihalis Yannakakis, « On the hardness of approximating minimization problems », Journal of the ACM, ACM, vol. 41, n^o 5,‎ 1994, p. 960-981 (ISSN 0004-5411, DOI 10.1145/185675.306789).
• 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.