Pemrograman linear integer dalam jumlah variabel logaritmik

Saya membaca bahwa pemrograman linear integer dapat dipecahkan dalam waktu polinominal jika jumlah variabel diperbaiki, yaitu . Jika jumlah variabel tumbuh secara logaritmik, yaitu untuk input ukuran , apakah masalahnya masih dapat dipecahkan dalam waktu polinominal atau apakah ini merupakan masalah terbuka? $n$ $n \in O(1)$ $n \in O(\log_2(N))$ $N$

cc.complexity-theory np open-problem pengguna3613886
sumber

Tidak bisakah Anda menambahkan kendala yang benar-benar sepele untuk meningkatkan ukuran input?

joro

Mengapa Anda ingin menambah ukuran input?

user3613886

Untuk membuat input sangat besar sehingga jumlah variabel adalah logaritmik dan sesuai dengan pertanyaan Anda.

joro

tetapi dalam pertanyaan kita sudah mengasumsikan bahwa variabel-variabel adalah logaritmik dibandingkan dengan ukuran input

user3613886

Saya berpikir untuk menjadikan semua instance sebagai milik Anda, tetapi ini mungkin secara eksponensial meningkatkan input.

joro

Jawaban:

Saya hanya bisa memberikan jawaban parsial untuk pertanyaan ini.

Sebuah hasil oleh Lenstra (yang kemudian diperbaiki oleh Kannan, dan Frank dan Tardos) menyatakan bahwa ILP dengan variabel dapat diselesaikan dalam waktu (dikalikan polinomial dalam ukuran ILP). Oleh karena itu, ILP dalam P ketika jumlah variabel adalah . Saya tidak yakin apakah algoritma diketahui, atau apakah algoritma seperti itu akan bertentangan dengan ETH. $k$ $k^{O(k)}$ $O(\log n/\log\log n)$ $2^{O(k)}$

Saya menemukan informasi ini dalam disertasi Daniel Lokshtanov. Berikut referensi yang relevan.

HW Lenstra. Pemrograman integer dengan sejumlah variabel tetap. Matematika Penelitian Operasi, 8: 538-548, 1983.
R. Kannan. Teorema tubuh cembung dan pemrograman bilangan bulat Minkowski. Matematika Penelitian Operasi, 12: 415-440, 1987.
Andras Frank dan Eva Tardos. Aplikasi pendekatan diophantine simultan dalam optimasi kombinatorial. Combinatorica, 7: 49–65, 1987.

Michael Lampis
sumber

Saya pikir Anda akan membutuhkan algoritma O (k ^ p) untuk p tetap, karena bahkan algoritma dengan 2 ^ O (k) akan bersifat eksponensial?

user3613886

Maaf, saya menggunakan notasi yang berbeda dari pertanyaan. Dengan

Maksudku jumlah variabel, dan

adalah ukuran input, sehingga

algoritma akan polinomial-waktu jika

k

$k$

n

$n$

2^{k}

$2^{k}$

k = O (\log n)

$k=O(\log n)$

Michael Lampis

Tapi misalkan Anda hanya memiliki variabel biner, bukankah brute force

2^{k}

$2^k$

user3613886

@ user3613886, tentu saja, tapi itu masalah / pertanyaan yang berbeda. Kami tidak dijanjikan dalam pertanyaan bahwa variabelnya adalah biner.

Tidak bisakah Anda menambahkan kendala yang benar-benar sepele untuk meningkatkan ukuran input?

joro