Complexité du problème de couverture d'intervalle

Considérons le problème$Q$ suivant Q : On nous donne un entier et k intervalles [ l i , r i ] avec 1 ≤ l i ≤ r i ≤ 2 n . On nous donne également 2 n entiers d 1 , … , d 2 n ≥ 0 . La tâche consiste à sélectionner un nombre minimum d'intervalles [ l i , r i$n$$k$$[l_i,r_i]$$1\leq l_i\leq r_i\leq 2n$$2n$$d_1,…,d_{2n}\geq 0$$[l_i,r_i]$de telle sorte que pour chaque , au moins d i intervalles contenant l'entier i sont sélectionnés.$i=1,…,2n$$d_i$$i$

Il n'est pas difficile de voir que peut être résolu en temps polynomial (voir ci-dessous).$Q$

Considérons maintenant le problème$Q’$ légèrement modifié Q 'suivant : L'entrée du problème est la même que précédemment. Cependant, la tâche consiste maintenant à sélectionner un nombre minimum d'intervalles tel que pour chaque , au moins d 2 i - 1 intervalles contenant l'entier 2 i - 1 ou au moins d 2 i intervalles contenant l'entier 2 i sont sélectionnés (avec «ou» nous entendons le ou logique habituel).$i=1,…,n$$d_{2i-1}$$2i-1$$d_{2i}$$2i$

Ma question: peut-il être résolu en temps polynomial?$Q’$

Voici deux façons de résoudre efficacement:$Q$

Un algorithme simple et gourmand: balayez les intervalles de gauche à droite et ne sélectionnez que le nombre d'intervalles nécessaire pour «satisfaire» les nombres . Chaque fois qu'il y a un choix entre différents intervalles, choisissez celui (s) avec le point final droit maximal.$d_i$

Un programme entier: pour chaque intervalle introduisez une variable de décision x i ∈ { 0 , 1 } avec x i = 1 si l'intervalle est sélectionné. L'objectif est de minimiser x 1 + … + x k , soumis aux contraintes ∑ j : i ∈ [ l j , r j ] x j ≥ d $[l_i,r_i]$$x_i\in\{0,1\}$$x_i=1$$x_1+…+x_k$$\sum_{j:i\in[l_j,r_j]} x_j\geq d_i$. La matrice de contraintes de ce programme entier a les propriétés consécutives et donc la relaxation de programmation linéaire de ce programme a une solution optimale entière.

Merci pour toutes les astuces, et aussi pour les références!

Chaque instance de Q peut être transformée en une instance du problème de couverture de plusieurs ensembles, où les emplacements sont les intervalles , couvrant une séquence consécutive de points de demande (= entiers d i ).$[l_i,r_i]$$d_i$