Seberapa cepat kita bisa menyelesaikan program linear integer yang benar-benar unimodular?

(Ini adalah tindak lanjut dari pertanyaan ini dan jawabannya .)

Saya memiliki program linear integer benar-benar unimodular (TU) berikut (ILP). Di sini semua bilangan bulat positif diberikan sebagai bagian dari input. Subset tertentu dari variabel diatur ke nol, dan sisanya dapat mengambil nilai integral positif:x i $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$$x_{ij}$

Memperkecil

$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$

Tunduk pada:

$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$

$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

Matriks koefisien dari bentuk standar adalah matriks dengan entri dari .- 1 , 0 , $(2\ell+m)\times \ell m$${-1,0,1}$

Pertanyaanku adalah:

Apa batas atas terbaik yang dikenal untuk waktu berjalan algoritma polinomial-waktu yang menyelesaikan ILP seperti itu? Bisakah Anda mengarahkan saya ke beberapa referensi tentang ini?

Saya melakukan pencarian, tetapi di sebagian besar tempat mereka berhenti dengan mengatakan bahwa TU ILP dapat diselesaikan dalam waktu polinomial menggunakan algoritma polinomial-waktu untuk LP. Satu hal yang tampak menjanjikan adalah makalah tahun 1986 oleh Tardos [1] di mana ia membuktikan bahwa masalah tersebut dapat diselesaikan dalam waktu polinomial dalam ukuran matriks koefisien. Sejauh yang saya tahu dari makalah, bagaimanapun, waktu berjalan dari algoritma itu tergantung pada gilirannya pada waktu berjalan dari algoritma waktu polinomial untuk memecahkan LP.

Apakah kita mengetahui algoritma yang memecahkan kasus khusus ini (TU ILP) secara signifikan lebih cepat daripada algoritma umum yang memecahkan masalah LP?

Jika tidak,

Algoritma mana untuk LP yang akan menyelesaikan ILP seperti itu yang tercepat (dalam arti asimptotik)?

[1] Algoritma yang sangat polinomial untuk menyelesaikan program linear kombinatorial, Eva Tardos, Riset Operasi 34 (2), 1986

Saya percaya Pada kelas matriks yang sepenuhnya unimodular , oleh Yannakakis, memberikan jawaban untuk pertanyaan Anda untuk kasus khusus TU ILP (setiap kali tidak ada siklus aneh dalam grafik bipartit yang diperoleh dengan melihat koefisien matriks sebagai matriks kedekatan).

Dalam makalah itu ada referensi untuk algoritma Polinomial untuk kelas program linier , yang tampaknya menangani semua matriks yang sama sekali unimodular, tetapi saya tidak yakin tentang seberapa jauh lebih efisien dibandingkan dengan algoritma generik untuk piringan hitam.

$O([n^3/\ln n]L)$

Telah ditunjukkan bahwa LP yang sepenuhnya unimodular dapat dipecahkan dalam waktu yang sangat polinomial di bawah "asumsi degenerasi" - tautan di sini (jadi jika ILP memiliki formulasi Totally Unimodular (TU) dengan asumsi yang sama maka algoritma ini akan menyelesaikan TU ILP, pada waktu polinomial yang kuat Ini adalah pengembangan dari metode Tardos, dan menyiratkan batas yang lebih ketat ke formulasi ILP TU (Totally Unimodular).