Pentingnya Integrality Gap

Saya selalu mengalami kesulitan dalam memahami pentingnya Integrality Gap (IG) dan terikat padanya. IG adalah rasio (kualitas) jawaban integer optimal untuk (kualitas) solusi nyata optimal dari relaksasi masalah. Mari kita pertimbangkan vertex cover (VC) sebagai contoh. VC dapat dinyatakan sebagai menemukan solusi integer optimal dari set persamaan linear berikut:

Kami memiliki nol / satu variabel bernilai s untuk setiap vertex dari grafik . Persamaannya adalah: untuk , dan untuk setiap tepi . Kami mencari nilai yang akan meminimalkan .$x_v$$v \in V(G)$$G$$0 \leq x_v \leq 1$$v\in V(G)$$1 \leq x_v+x_u$$uv \in E(G)$$\sum_{v \in V(G)} x_v$

Relaksasi masalah ini memungkinkan nilai nyata antara dan sehingga ruang solusi lebih besar dan solusi nyata yang optimal dapat lebih kecil dari solusi integer optimal yang ingin kita temukan. Oleh karena itu kita perlu melakukan proses "pembulatan" pada jawaban nyata optimal yang diperoleh dari pemrograman linier untuk menemukan solusi integer. Solusi integer optimal akan berada di antara solusi nyata optimal dan hasil dari proses pembulatan. IG adalah rasio dari solusi integer optimal ke solusi nyata optimal dan tidak mengatakan apa-apa tentang proses pembulatan. Proses pembulatan dapat (secara teori) sepenuhnya mengabaikan solusi nyata dan menghitung solusi integer optimal secara langsung.$0$$1$

Mengapa orang tertarik untuk membuktikan batasan pada IG?

Kesenjangan integralitas pada dasarnya mewakili batas-batas inheren dari relaksasi linear atau cembung tertentu dalam mendekati suatu program integer. Secara umum, jika kesenjangan integral relaksasi tertentu adalah , maka setiap algoritma pendekatan berdasarkan relaksasi itu tidak dapat berharap untuk melakukan lebih baik daripada pendekatan- . Jadi setidaknya, kesenjangan integral menarik bagi perancang algoritma karena mereka menyarankan keterbatasan dalam teknik tertentu. $x$$x$

Jadi mengapa tidak membuat relaksasi LP lain atau beralih ke teknik lain dan melanjutkan? Pemrograman linear dan cembung telah terbukti menjadi pusat algoritma perkiraan; untuk banyak masalah, kesenjangan integral dari formulasi LP atau SDP alami sama dengan rasio aproksimasi dari algoritma terbaik dan juga kekerasan dari rasio aproksimasi. Ini hanya pengamatan empiris, tetapi itu berarti bahwa membuktikan kesenjangan integral dapat menyarankan konsekuensi yang jauh lebih kuat dari peningkatan algoritma atau batas bawah.

Mungkin ada alasan yang lebih dalam dan lebih keras untuk fenomena ini. Sebagai contoh, dengan asumsi dugaan permainan yang unik, diketahui bahwa rasio perkiraan dan rasio ketidakpastian untuk masalah kepuasan kendala sama dengan kesenjangan integral dari relaksasi SDP sederhana (lihat Algoritma Optimal dan Hasil Ketidakmungkinan Diharapkan untuk Setiap CSP? Oleh Prasad Raghavendra)

Akhirnya, kesenjangan integral mewakili batas bawah tanpa syarat . Biasanya, kita perlu mengandalkan asumsi yang tidak terbukti (mis. ) jika kita ingin membuat kemajuan dalam batas bawah, tetapi untuk model perhitungan yang terbatas, kita kadang-kadang bisa pergi tanpa itu (lihat catatan kuliah oleh Luca Trevisan). Kesenjangan integral, yang murni geometris daripada komputasi, adalah salah satu cara untuk mendapatkan batas bawah yang cukup kuat tanpa beban asumsi tambahan.$P \neq NP$

Misalkan masalah Anda menarik adalah masalah minimisasi dan bahwa Anda telah mengembangkan algoritma -approximate. Jika, pada input yang diberikan, algoritma Anda menghasilkan solusi biaya , maka perhitungan algoritma ditambah analisisnya memberikan sertifikat bahwa, pada input tersebut, optimal adalah setidaknya . Jelas, adalah setidaknya yang optimal, jadi untuk setiap input kami dapat menyatakan batas bawah ke optimal yang setidaknya merupakan fraksi dari optimum itu sendiri.c a / c a 1 /$a$$c$$a/c$$a$$1/c$

Dalam semua algoritme yang didasarkan pada relaksasi cembung (LP dan SDP) yang saya ketahui, ikatan bawah bersertifikat ke optimum diberikan oleh relaksasi yang optimal. Jika relaksasi memiliki kesenjangan integral , maka tidak mungkin untuk mencapai rasio aproksimasi lebih baik daripada , kecuali dalam analisis seseorang memperkenalkan teknik batas bawah untuk optimum yang lebih kuat daripada batas bawah yang disediakan oleh relaksasi.$I$$I$

Kesenjangan integral adalah indikator yang berguna tentang seberapa baik IP dapat diperkirakan. Mungkin lebih baik untuk memikirkannya secara informal dan intuitif. Kesenjangan integral yang tinggi menyiratkan bahwa metode tertentu tidak akan berfungsi. Metode primal / rangkap tertentu, misalnya, bergantung pada celah integral kecil. Untuk LP Vertex Primal standar standar, LP ganda meminta pencocokan maksimum. Dalam hal ini, kita dapat melakukan hal berikut:

• temukan solusi pecahan yang optimal ke LP ganda (pencocokan pecahan maksimum)$\boldsymbol{y}$
• kalikan solusi dengan faktor 2 (gandakan semua ujung bobot)$\boldsymbol{y}$
• ubah ini menjadi integral untuk LP primal (masing-masing sisi memberi setengah bobotnya dari vektor ke masing-masing titik akhir dalam vektor , kemudian masing-masing adalah diganti dengan ).$\boldsymbol{x}$$2\boldsymbol{y}$$\boldsymbol{x}$$x_i$$\min(\lfloor x_i\rfloor, 1)$

Dalam hal ini strategi sederhana ini bekerja dan kami berakhir dengan solusi integral yang layak untuk LP primal yang beratnya tidak lebih dari dua kali berat solusi layak untuk LP ganda. Karena bobot solusi yang layak untuk LP ganda adalah batas bawah untuk OPT, ini adalah algoritma 2-aproksimasi.

Sekarang, di mana celah integral datang? IG adalah 2 dalam hal ini, tetapi itu saja tidak menyiratkan bahwa algoritma akan berfungsi. Sebaliknya, ini menunjukkan bahwa itu mungkin berhasil. Dan jika IG lebih dari 2, itu akan menjamin bahwa strategi sederhana tidak akan selalu berhasil. Paling tidak kita harus melipatgandakan solusi ganda oleh IG. Jadi, kesenjangan integral terkadang memberi tahu kita apa yang tidak akan berhasil. Kesenjangan integralitas juga dapat menunjukkan faktor aproksimasi seperti apa yang dapat kita harapkan. Kesenjangan integral kecil menunjukkan bahwa menyelidiki strategi pembulatan, dll, mungkin merupakan pendekatan yang bermanfaat.

Untuk contoh yang lebih menarik, pertimbangkan masalah Hitting Set dan teknik yang kuat untuk mendekati masalah menggunakan net (Brönnimann & Goodrich, 1995) . Banyak masalah dapat dirumuskan sebagai contoh dari Hitting Set, dan strategi yang telah berhasil untuk banyak masalah adalah dengan melakukan ini, kemudian cari saja pencari bersih yang bagus, yaitu algoritma untuk membangun jaring kecil, dan memutar semuanya melalui meta-algoritma B&G. Jadi orang-orang (termasuk saya) mencoba mencari pencari bersih untuk contoh terbatas dari Hitting Set yang, untuk apa pun , dapat membangun -net ukuran , di mana fungsi$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$f(1/\varepsilon)$$f$harus sekecil mungkin. Memiliki adalah tujuan umum; ini akan memberikan pendekatan .$f(1/\varepsilon) = \mathcal{O}(1/\varepsilon)$$\mathcal{O}(1)$

Ternyata, yang terbaik yang mungkin fungsi dibatasi oleh celah integralistik dari LP tertentu untuk Menekan Set (Bahkan, Rawitz, Shahar, 2005) . Secara khusus, solusi integral dan fraksional optimal memenuhi . Untuk instance Hitting Set yang tidak dibatasi, kesenjangan integralnya adalah , tetapi ketika merumuskan masalah lain seperti Hitting Set, IG bisa lebih rendah. Dalam contoh ini penulis menunjukkan cara menemukan -jala ukuran$f$$\mathrm{OPT}_I \leq f(\mathrm{OPT}_f)$$\Theta(\log(m))$$\varepsilon$$\mathcal{O}((1/\varepsilon) \log \log (1/\varepsilon))$untuk contoh terbatas dari Hitting Set yang sesuai dengan masalah memukul kotak paralel-sumbu. Dengan cara ini mereka meningkatkan faktor perkiraan yang paling dikenal untuk masalah itu. Ini masalah terbuka apakah ini bisa diperbaiki atau tidak. Jika, untuk instance Hitting Set yang terbatas ini, IG untuk Hitting Set LP adalah , tidak mungkin untuk merancang penjaring penemu net jaring ukuran , karena melakukan hal itu akan menyiratkan adanya suatu algoritma yang menjamin integral memukul set ukuran , tetapi sejak$\Theta(\log \log m)$$\varepsilon$$o((1/\varepsilon) \log \log (1/\varepsilon))$$o(\mathrm{OPT}_f \log\log \mathrm{OPT}_f)$$\mathrm{OPT}_f\leq m$ini akan menyiratkan kesenjangan integral yang lebih kecil. Jadi, jika kesenjangan integral besar, membuktikannya bisa mencegah orang membuang-buang waktu mencari pencari jaring yang bagus.

Ketika Anda datang dengan algoritma perkiraan untuk beberapa masalah maksimalisasi NP-keras, ada beberapa nilai yang mungkin Anda pedulikan: Ada OPT, nilai optimal masalah Anda, yang sama dengan OPT (IP), optimal nilai formulasi IP yang benar dari masalah Anda. Ada juga OPT (LP), nilai optimal dari relaksasi linear IP Anda.

$OPT(LP) \geq OPT(IP)$

Akhirnya, ada V, nilai solusi yang akhirnya Anda dapatkan dengan membulatkan solusi LP. Anda ingin dapat membuktikan bahwa untuk menunjukkan bahwa algoritma Anda adalah pendekatan , tetapi seringkali tidak mungkin untuk melakukan ini secara langsung, karena Anda tidak memiliki bertahan di ruang solusi. Sebaliknya, yang hampir selalu terbukti adalah bahwa . Ini tentu saja menyiratkan , tetapi lebih kuat. Secara khusus, jika kesenjangan integral formulasi IP Anda lebih besar dari , pernyataan di atas akan salah secara umum, karena prosedur pembulatan Anda berakhir dengan solusi integral.$V > \frac{OPT(IP)}{c}$$c$$V \geq \frac{OPT(LP)}{c}$$V > \frac{OPT(IP)}{c}$$c$

Jadi intinya adalah ini: LP memberi Anda solusi yang Anda tahu adalah "baik", dan Anda ingin membulatkannya ke sesuatu yang "hampir sama baiknya". Jika kesenjangan integral besar, ini tidak mungkin secara umum, karena tidak akan pernah ada prosedur yang dijamin untuk mendapatkan solusi integral yang "sama bagusnya" dengan solusi LP - karena kadang-kadang, ini tidak ada!

Anda benar bahwa kesenjangan integral relaksasi tidak ada hubungannya dengan algoritma pembulatan. Ini adalah dua pengertian yang berbeda. Kesenjangan integralitas adalah properti dari relaksasi tertentu. Artinya, seberapa besar nilai relaksasi itu dibandingkan dengan nilai integral optimal?

Mengapa kita peduli dengan relaksasi linier / cembung? Untuk memperkirakan nilai integral secara efisien. Karenanya, kami biasanya berbicara tentang relaksasi hanya dalam kasus-kasus di mana nilai optimal sulit untuk dihitung dan kami tertarik pada pendekatan yang efisien. Kesenjangan integral menunjukkan kepada kita keterbatasan yang melekat dari apa yang dapat dicapai dengan teknik-teknik tersebut.

Jadi, mengapa kita peduli tentang pembulatan algoritma di atas relaksasi? Kami menggunakan algoritma pembulatan untuk memecahkan masalah algoritmik dalam menemukan solusi yang mendekati optimal dan bukan hanya mendekati nilai solusi yang optimal. Selain itu, algoritma pembulatan sering digunakan untuk mengikat kesenjangan integral dari relaksasi di tempat pertama.

Secara teknis, kesenjangan integral adalah untuk formulasi IP spesifik, bukan (seperti yang Anda rumuskan) ransum antara relaksasi linier terbaik dan solusi optimal (yang tampak untuk mengukur lebih dari SEMUA formulasi IP).

Kesenjangan integralitas penting karena menunjukkan batas formulasi LP tertentu yang digunakan. Jika saya tahu bahwa relaksasi tertentu memiliki celah integralitas , maka saya juga tahu bahwa jika saya berharap untuk membuktikan ikatan yang lebih baik daripada , saya akan perlu menggunakan formulasi yang berbeda.$c$$c$

Ada makalah yang sangat menarik "Pada keuntungan pengkodean jaringan untuk meningkatkan throughput jaringan" yang menunjukkan bahwa kesenjangan integral dari "relaksasi pemotongan bidirected" untuk masalah pohon Steiner persis sama dengan jenis "keuntungan pengkodean" dalam komunikasi jaringan. Saya tidak tahu banyak makalah serupa lainnya. Namun, kita juga harus mencatat bahwa relaksasi LP yang tampaknya lebih baik untuk masalah pohon Steiner diketahui (misalnya, lihat algoritme aproksimasi LP berbasis hypergraphic baru dari Byrka dkk di STOC 2010, saya juga dengan sukarela menjadi sukarelawan karena saya turut menulis beberapa makalah baru-baru ini mempelajari hipergrafik LP).

Sebagian besar jawaban telah membahas alasan utama untuk peduli tentang kesenjangan integral, yaitu, bahwa algoritma pendekatan hanya berdasarkan penggunaan ikatan yang disediakan oleh relaksasi tidak dapat berharap untuk membuktikan rasio yang lebih baik daripada kesenjangan integral. Biarkan saya memberi dua alasan meta lain mengapa kesenjangan integral adalah panduan yang berguna. Untuk kelas besar masalah optimasi kombinatorial, kesetaraan pemisahan dan optimasi menunjukkan bahwa algoritma yang tepat terkait erat dengan lambung cembung dari solusi yang layak untuk masalah tersebut. Dengan demikian perspektif geometris dan algoritmik sangat terkait erat. Kesetaraan formal yang serupa tidak dikenal untuk algoritma aproksimasi tetapi merupakan panduan yang berguna - algoritma berjalan seiring dengan relaksasi geometris. Inovasi algoritmik terjadi ketika orang memiliki target nyata untuk meningkat.