Complejidad del problema de cobertura de intervalo

Considere el siguiente problema $Q$ : Se nos da un número entero , y k intervalos [ l i , r i ] con 1 ≤ l i ≤ r i ≤ 2 n . También se nos dan 2 n enteros d 1 , ... , d 2 n ≥ 0 . La tarea es seleccionar un número mínimo de intervalos [ 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]$tal que para cada , se seleccionan al menos d i intervalos que contienen el número entero i .$i=1,…,2n$$d_i$$i$

No es difícil ver que puede resolverse en tiempo polinómico (ver más abajo).$Q$

Ahora considere el siguiente problema $Q’$ ligeramente modificado : La entrada del problema es la misma que antes. Sin embargo, la tarea ahora es seleccionar un número mínimo de intervalos de modo que para cada , al menos d 2 i - 1 intervalos que contengan el entero 2 i - 1 o al menos d 2 i intervalos que contengan el entero 2 i están seleccionados (con "o" nos referimos a la lógica habitual o).$i=1,…,n$$d_{2i-1}$$2i-1$$d_{2i}$$2i$

Mi pregunta: ¿Se puede resolver en tiempo polinómico?$Q’$

Aquí hay dos formas de resolver eficientemente:$Q$

Un algoritmo codicioso simple: recorra los intervalos de izquierda a derecha y seleccione solo los intervalos necesarios para "satisfacer" los números . Siempre que haya una opción entre diferentes intervalos, elija uno (s) con el punto final derecho máximo.$d_i$

Un programa entero: para cada intervalo introduzca una variable de decisión x i ∈ { 0 , 1 } con x i = 1 si se selecciona el intervalo. El objetivo es minimizar x 1 + … + x k , sujeto a las restricciones ∑ 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 matriz de restricción de este programa entero tiene las propiedades consecutivas y, por lo tanto, la relajación de la programación lineal de este programa tiene una solución óptima entera.

Gracias por cualquier pista, y también por referencias!

Cada instancia de Q puede transformarse en una instancia del problema de cobertura de conjunto múltiple, donde las ubicaciones son los intervalos , que cubren una secuencia consecutiva de puntos de demanda (= enteros d i ).$[l_i,r_i]$$d_i$