Dokładne algorytmy czasu wykładniczego dla programów 0-1 z danymi nieujemnymi

9

Czy są znane algorytmy dla następującego problemu, które pokonały naiwny algorytm?

Dane wejściowe: matryca $A$ i wektory $b,c$ , gdzie wszystkie wpisy z pozycji $A,b,c$ są liczbami całkowitymi nieujemnymi.

Wyjście: optymalne rozwiązanie $x^*$ do $\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}$ .

To pytanie jest udoskonaloną wersją mojego poprzedniego pytania Dokładne algorytmy czasu wykładniczego dla programowania 0-1 .

np-hardness integer-programming exp-time-algorithms

— Austin Buchanan
źródło

5

jeśli liczba niezerowych współczynników w $A$ jest liniowa w $n$ , istnieje algorytm, który rozwiązuje ten problem w czasie krótszym niż $2^n$ .

Oto jak to działa. Używamy standardowego połączenia między problemem optymalizacji a odpowiadającym mu problemem decyzyjnym. Aby przetestować, czy istnieje rozwiązanie którym i , utworzymy problem decyzyjny: dołączymy ograniczenie do macierzy i przetestujemy czy istnieje takie , że i . W szczególności utworzymy nową macierz , biorąc i dodając dodatkowy wiersz zawierający , i utworzymy , biorąc $x$ $Ax\le b$ $c^T x \ge \alpha$ $c^T x\ge \alpha$ $A$ $x$ $Ax \le b$ $-c^T x \le -\alpha$ $A'$ $A$ $-c^T$ $b'$ $b$ i sąsiadujący dodatkowy wiersz z . Otrzymujemy problem decyzyjny: czy istnieje taki, że ? Odpowiedź na ten problem decyzyjny mówi nam, czy istnieje rozwiązanie pierwotnego problemu optymalizacji o wartości lub większej. Ponadto, jak wyjaśniono w odpowiedzi na poprzednie pytanie , ten problem decyzyjny można rozwiązać w czasie krótszym niż , jeśli liczba niezerowych współczynników w jest liniowa w (a zatem jeśli liczba nie- zerowe współczynniki w są liniowe w ). Teraz możemy korzystać z wyszukiwania binarnego na $-\alpha$ $x \in \{0,1\}^n$ $A' x \le b'$ $\alpha$ $2^n$ $A'$ $n$ $A$ $n$ $\alpha$ rozwiązać problem optymalizacji w czasie krótszym niż . $2^n$

Dziękuję AustinBuchanan i Stefanowi Schneiderowi za pomoc w debugowaniu wcześniejszej wersji tej odpowiedzi.

— DW
źródło

Czy możesz podać mocniejszą odpowiedź: na przykład „istnieje algorytm ” lub „algorytm szybszy niż obaliłby ...”?

O (2^{n / 2})

$O(2^{n/2})$

O (2^{n})

$O(2^n)$

— Austin Buchanan,

@AustinBuchanan, jeśli liczba wymiarów jest wystarczająco mała, istnieje algorytm , jak udokumentowano w mojej odpowiedzi na inne pytanie . To najlepsze, co wiem, jak to zrobić; Nie wiem jak to zrobić lepiej. Może inni będą w stanie udzielić silniejszej odpowiedzi!

b

$b$

O^{*} (2^{n / 2})

$O^*(2^{n/2})$

— DW

O^{*} (2^{n / 2})

$O^*(2^{n/2})$ utrzymuje się zawsze, gdy liczba ograniczeń wynosi ?

O (1)

$O(1)$

— Austin Buchanan

4

Jeśli weźmiemy pod uwagę problem minimalizacji , to następująca redukcja pokazuje, że algorytm działa w czasie dla obaliłby SETH. Przeformułowanie potwierdza ten sam wynik dla zamierzonego problemu (wersja maksymalizacyjna). $\min_y \{c^T y : Ay \ge b, y \in \{ 0,1\}^n \}$ $O(2^{\delta n/2})$ $\delta <1$

Biorąc pod uwagę instancję CNF-SAT ze zmiennymi , sformułuj 0-1 IP z dwiema zmiennymi dla każdej zmiennej w instancji SAT. Jak zwykle klauzula byłaby reprezentowana jako . Następnie dla każdej zmiennej w instancji SAT dodaj ograniczenie . Celem jest zminimalizowanie . Cel OD będzie IFF instancji SAT jest spe. $\Phi = \wedge_{i=1}^m C_i$ $\{x_j \}_{j=1}^n$ $y_j, \overline{y}_j$ $x_j$ $(x_1 \vee \overline{x}_2 \vee x_3)$ $y_1 + \overline{y}_2 + y_3 \ge 1$ $x_j$ $y_j + \overline{y}_j \ge 1$ $\sum_{j=1}^n (y_j + \overline{y}_j)$ $n$

Podziękowania dla Stefana Schneidera za korektę.

Aktualizacja: w On On Problems Hard jak CNF-Sat autorzy przypuszczają, że SET COVER nie może być rozwiązany w czasie , , gdzie odnosi się do liczby zestawów. Jeśli to prawda, to pokazuje, że mojego problemu nie można rozwiązać również w czasie . $O(2^{\delta n})$ $\delta <1$ $n$ $O(2^{\delta n})$

Aktualizacja 2. O ile mogę stwierdzić, zakładając SETH, mojego problemu nie można rozwiązać w czasie , ponieważ wykazano, że nie można ustawić zestawu uderzeń (z zestawem naziemnym o rozmiarze ) rozwiązane w czasie . $O(2^{\delta n})$ $n$ $O(2^{\delta n})$

— Austin Buchanan
źródło

3

Ponieważ podwoiłeś liczbę zmiennych, myślę, że to pokazuje tylko, że algorytm dla tego problemu z czasem wykonania byłby sprzeczny z SETH.

O (2^{δ n / 2})

$O(2^{\delta n/2})$

— Stefan Schneider,

Wait ... autorzy z Problematyki twardy jak stan CNF-SAT, że "dla każdego , Algorytm Uderzanie Set naruszałyby Seth." Czy to nie działa?

ϵ < 1

$\epsilon <1$

O (2^{ϵ n})

$O(2^{\epsilon n})$

\dots

$\dots$

— Austin Buchanan