Mengapa kelonggaran komplementer penting?

Slackness komplementer (CS) umumnya diajarkan ketika berbicara tentang dualitas. Ini membangun hubungan yang bagus antara primal dan kendala ganda / variabel dari sudut pandang matematika.

Dua alasan utama untuk menerapkan CS (seperti yang diajarkan di kursus pascasarjana dan buku teks):

Untuk memeriksa optimalitas LP
Untuk membantu memecahkan masalah dual

Mengingat kekuatan komputasi saat ini dan algoritma polinomial untuk menyelesaikan piranti lunak apakah CS masih relevan dari sudut pandang pragmatis? Kami selalu bisa menyelesaikan masalah dual dan mengatasi kedua poin di atas. Saya setuju bahwa "lebih efisien" untuk menyelesaikan dual dengan bantuan CS tetapi apakah itu? Atau ada lebih banyak CS daripada memenuhi mata? Di mana tepatnya CS bermanfaat di luar dua poin di atas ? Saya biasanya melihat teks yang menyinggung konsep CS ketika berbicara tentang algoritma aproksimasi tapi saya gagal memahami perannya di sana.

ds.algorithms approximation-algorithms linear-programming primal-dual PhD
sumber

Bukan bidang keahlian saya, tapi sepertinya Anda bertanya mengapa kami mengajarkan properti X meskipun memutuskan X itu mudah secara komputasi. Misalnya, mengapa kita mengajarkan karakterisasi "tidak ada siklus aneh = bipartit" tentang bipartiteness walaupun kita memiliki algoritma waktu polinomial untuk memeriksa bipartiteness. Apakah itu yang Anda tanyakan, dalam beberapa hal?

Robin Kothari

Tidak persis. Saya mengerti "mengapa" Anda mengajarkannya. Saya ingin tahu dari POV praktis bagaimana ini digunakan ketika memecahkan piringan hitam dan / atau merancang algoritma perkiraan. Apa wawasan yang kita dapatkan selain hubungan matematika antara variabel dan batasan.

PhD

Yah, saya pikir itu bisa membantu dengan mendapatkan solusi "analitik" ... yang mungkin lebih sulit didapatkan dengan komputer.

usul

Saya tidak "mendapatkan" pertanyaan itu. Hanya karena kita menggunakan kalkulator dan komputer untuk menambah dan mengalikan angka, apakah kita masih perlu mengetahui properti angka?

Chandra Chekuri

@ChandraChekuri - Saya tidak bermaksud begitu. Saya hanya mencoba mencari tahu apa yang hebat tentang teorema ini dan apa yang membuatnya penting. Saya tidak ingin menerimanya sebagai "begitulah adanya" tetapi ingin memiliki pemahaman yang lebih dalam tentang pentingnya wrt LP dualitas

PhD

Slackness komplementer adalah kunci dalam mendesain algoritma primal-dual. Ide dasarnya adalah:

$y$
$x$ $(x, y)$
$x$ $y$

$s$ $t$ $s$ $t$

Algoritma primal-dual bagus untuk banyak alasan. Secara filosofis, mereka memberikan lebih banyak wawasan daripada algoritma generik. Mereka biasanya memberikan algoritma waktu polinomial yang kuat, sedangkan kita masih belum memiliki pemecah LP polinomial yang kuat. Mereka seringkali lebih praktis daripada algoritma generik. Ini terutama benar jika kita tidak dapat menuliskan LP secara eksplisit dan satu-satunya pilihan kita yang lain adalah algoritma ellipsoid, yang merupakan kasus dengan pencocokan non-bipartit dan algoritma primal-dual Edmonds.

$y$ $x$ $y$ $x_i > 0$ $y_j > 0$ $x$ $\alpha$ $\alpha$

Sasho Nikolov
sumber

Mengapa kelonggaran komplementer penting?

Jawaban: