Złożoność problemu pokrycia interwałów

Rozważmy następujący problem$Q$ : Otrzymujemy liczbę całkowitą i przedziałów z . także liczb całkowitych . Zadanie polega na wybraniu minimalnej liczby przedziałów$n$$k$$[l_i,r_i]$$1\leq l_i\leq r_i\leq 2n$$2n$$d_1,…,d_{2n}\geq 0$ , że dla każdego i = 1 , ... , 2 n , co najmniej d ı odstępach zawierających całkowitą i są zaznaczone.$[l_i,r_i]$$i=1,…,2n$$d_i$$i$

Nietrudno dostrzec, że można rozwiązać w czasie wielomianowym (patrz poniżej).$Q$

Teraz rozważ następujący nieznacznie zmodyfikowany problem $Q’$ : Wkład problemu jest taki sam jak poprzednio. Teraz zadaniem jest jednak wybranie minimalnej liczby przedziałów, tak aby dla każdego , co najmniej d 2 i - 1 przedziałów zawierających liczbę całkowitą 2 i - 1 lub co najmniej d 2 i przedziałów zawierających liczbę całkowitą 2 i są wybrane („lub” oznacza zwykłą logiczną lub).$i=1,…,n$$d_{2i-1}$$2i-1$$d_{2i}$$2i$

Moje pytanie: Czy można rozwiązać w czasie wielomianowym?$Q’$

Oto dwa sposoby skutecznego rozwiązania :$Q$

Prosty chciwy algorytm: przeciągnij przedziały od lewej do prawej i wybierz tylko tyle przedziałów, ile potrzeba, aby „spełnić” liczby . Ilekroć istnieje wybór między różnymi przedziałami, wybierz ten (y) z maksymalnym prawym punktem końcowym.$d_i$

Program całkowita: Dla każdego przedziału Wprowadzenie zmienną decyzyjną x i ∈ { 0 , 1 } z X i = 1, wtedy i tylko wtedy wybiera się odstęp. Celem jest zminimalizowanie x 1 + … + x k , z zastrzeżeniem ograniczeń ∑ 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$. Macierz ograniczeń tego programu liczb całkowitych ma kolejną właściwość jedynek, a zatem relaksacja programowania liniowego tego programu ma optymalne rozwiązanie liczb całkowitych.

Dzięki za wszelkie wskazówki, a także za referencje!

Każde wystąpienie Q może być przekształcona w instancji zestaw kilku pokrywy problemu, w których lokalizacje są odstępy , obejmujący sekwencję kolejnych punktów na żądanie (= całkowite d I ).$[l_i,r_i]$$d_i$