Algoritma eksponensial waktu yang tepat untuk program 0-1 dengan data tidak negatif

Apakah ada algoritma yang dikenal untuk masalah berikut yang mengalahkan algoritma naif?

Input: matriks $A$ dan vektor $b,c$ , di mana semua entri $A,b,c$ adalah bilangan bulat tidak negatif.

$x^*$$\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}$

Pertanyaan ini adalah versi yang disempurnakan dari pertanyaan saya sebelumnya Algoritma eksponensial waktu yang tepat untuk pemrograman 0-1 .

jika jumlah koefisien tidak nol dalam adalah linier dalam , ada algoritma yang menyelesaikan masalah ini dalam waktu kurang dari waktu.$A$$n$$2^n$

Begini cara kerjanya. Kami menggunakan koneksi standar antara masalah optimisasi dan masalah keputusan terkait. Untuk menguji apakah ada solusi mana dan , kami akan membentuk masalah keputusan: kami akan menggabungkan kendala ke matriks , dan menguji apakah ada sehingga dan . Secara khusus, kita akan membentuk matriks dengan mengambil dan menambahkan baris tambahan yang mengandung , dan kita akan membentuk dengan mengambil$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$dan bersebelahan dengan baris tambahan dengan . Kami mendapatkan masalah keputusan: apakah ada sehingga ? Jawaban untuk masalah keputusan ini memberi tahu kami apakah ada solusi untuk masalah optimasi asli dari nilai atau lebih besar. Selain itu, seperti yang dijelaskan dalam jawaban untuk pertanyaan Anda sebelumnya , masalah keputusan ini dapat diselesaikan dalam waktu kurang dari kali, jika jumlah koefisien tidak nol dalam adalah linear dalam (dan dengan demikian jika jumlah non- nol koefisien dalam adalah linier dalam ). Sekarang kita dapat menggunakan pencarian biner di$-\alpha$$x \in \{0,1\}^n$$A' x \le b'$$\alpha$$2^n$$A'$$n$$A$$n$$\alpha$untuk menyelesaikan masalah pengoptimalan Anda dalam waktu kurang dari kali.$2^n$

Terima kasih saya kepada AustinBuchanan dan Stefan Schneider karena telah membantu men-debug versi sebelumnya dari jawaban ini.

Jika kita mempertimbangkan masalah minimalisasi , maka pengurangan berikut ini menunjukkan bahwa suatu algoritma berjalan dalam waktu untuk akan menyangkal SETH. Reformulasi membuktikan hasil yang sama untuk masalah yang dimaksudkan (versi maksimalisasi).$\min_y \{c^T y : Ay \ge b, y \in \{ 0,1\}^n \}$$O(2^{\delta n/2})$$\delta <1$

Diberikan instance dari CNF-SAT dengan variabel , merumuskan IP 0-1 dengan dua variabel untuk setiap variabel dalam instance SAT. Seperti biasa, klausa akan direpresentasikan sebagai . Kemudian untuk setiap variabel dalam instance SAT, tambahkan batasan . Tujuannya adalah untuk meminimalkan . Tujuan dari IP akan menjadi jika turunan SAT memuaskan.$\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$

Terima kasih kepada Stefan Schneider untuk koreksi.

Pembaruan: pada Nyala Sekeras CNF-Sat , penulis menduga bahwa SET COVER tidak dapat diselesaikan dalam waktu , , di mana mengacu pada jumlah set. Jika benar, ini akan menunjukkan bahwa masalah saya tidak dapat diselesaikan pada waktu juga.$O(2^{\delta n})$$\delta <1$$n$$O(2^{\delta n})$

Pembaruan 2. Sejauh yang saya tahu, dengan asumsi SETH, masalah saya tidak dapat diselesaikan dalam waktu , karena telah ditunjukkan bahwa Hitting Set (dengan ukuran dasar ground ) tidak dapat diselesaikan dipecahkan dalam waktu .$O(2^{\delta n})$$n$$O(2^{\delta n})$