Gap integralitas dan rasio aproksimasi

Ketika kami mempertimbangkan algoritma aproksimasi untuk masalah minimisasi, kesenjangan integral dari formulasi IP untuk masalah ini memberikan batas yang lebih rendah dari rasio aproksimasi untuk kelas algoritma tertentu (seperti pembulatan atau algoritma primal-dual). Bahkan, ada banyak masalah yang rasio perkiraan terbaiknya cocok dengan kesenjangan integral.

Beberapa algoritma mungkin memiliki rasio aproksimasi yang lebih baik daripada gap integral untuk beberapa masalah, tapi saya tidak tahu apakah contoh seperti itu ada atau tidak. Jika jawabannya ya, bisakah Anda memberikan beberapa contoh?

Saya tahu bahwa beberapa masalah menerima beberapa formulasi matematika. Dalam kasus seperti itu, pertimbangkan formulasi matematis dengan celah integral terkecil, selama itu dapat diselesaikan dalam waktu polinomial (mungkin beberapa formulasi dapat menggunakan oracle pemisahan).

Pertanyaan ini terkait dengan [pertanyaan: Pentingnya Celah Integralitas] .

ds.algorithms approximation-algorithms linear-programming integrality-gap Snowie
sumber

Saya akan menebak bahwa geometrik TSP akan menjadi contoh masalah seperti itu, tetapi saya tidak punya referensi.

Jukka Suomela

Dan bagaimana dengan masalah yang mengakui PTAS menggunakan strategi pergeseran? Apakah ada di antara mereka yang memiliki formulasi IP dengan kesenjangan integral kecil yang sewenang-wenang?

Jukka Suomela

@Jukka geometric TSP adalah contoh yang bagus. Contoh 4/3 integrality gap adalah metrik jalur terpendek pada grafik planar, dan harus dimungkinkan untuk menjadi instance dari Euclidean TSP atau

TSP di pesawat dengan gap

ℓ_{1}

$\ell_1$

1 + ϵ

$1+\epsilon$

Luca Trevisan

Saya mendengarnya disebut sebagai pertanyaan terbuka yang menarik apakah PTAS untuk masalah pada grafik planar dapat diwujudkan dengan menggunakan sejumlah tingkat relaksasi Sherali-Adams atau Lasserre yang konstan. (Di mana konstanta bergantung pada rasio perkiraan yang ingin dicapai seseorang.) Harus diketahui, atau setidaknya dapat dibuktikan dengan teknik saat ini, bahwa masalah grafik yang memiliki PTAS dalam grafik padat (mis. Potongan maksimum) juga memiliki keluarga polinomial ukuran relaksasi dengan celah integral kecil yang sewenang-wenang.

Luca Trevisan

Pertanyaan terkait: Apakah ada masalah yang terbukti bahwa LP ukuran polinomial tidak dapat memberikan rasio perkiraan yang paling dikenal saat ini? Apakah mungkin membuktikan hal seperti itu, bahkan untuk beberapa jenis piringan hitam terbatas?

Danu

Jawaban:

Seperti yang ditunjukkan, ada beberapa contoh.

Contoh klasik adalah pencocokan maksimum, di mana relaksasi "alami" (tanpa kendala set ganjil) memiliki celah 2, sementara tentu saja ada algoritma yang efisien. Yang satu ini tidak sepenuhnya memenuhi syarat, karena ada LP berukuran eksponensial yang dapat diselesaikan melalui ellipsoid.

Yang menarik adalah lokasi fasilitas berkapasitas. Di sini relaksasi alami memiliki kesenjangan integral yang tak terbatas. Namun algoritma pencarian berbasis lokal memberikan perkiraan faktor konstan.

Satu lagi yang sangat menarik (meskipun ini adalah masalah maksimalisasi) adalah makalah ini: http://www.cis.upenn.edu/~sanjeev/postscript/FOCS09_MaxMin.pdf . Di sini LP memiliki celah yang besar, namun algoritma yang menggunakan LP itu dapat melakukan yang lebih baik.

Kunal
sumber

Terima kasih banyak. Jawaban ini berisi apa yang saya cari, terutama makalah FOCS yang ditulis oleh Chakrabarty et al. (makalah ini sangat menarik minat saya). Karena itu saya menetapkan jawaban ini sebagai diterima. Saya masih mencari lebih banyak contoh dan karenanya siapa pun yang dapat memberikan contoh lain akan sangat dihargai.

Snowie

Ada berbagai contoh di mana relaksasi pemrograman semidefinite memungkinkan pendekatan yang lebih baik dari kesenjangan integral yang diketahui untuk relaksasi pemrograman linier.

Sebagai contoh, relaksasi pemrograman linier standar dari max cut memiliki kesenjangan integral 1/2, dan ini benar bahkan untuk relaksasi pemrograman linear yang jauh lebih canggih (cf de la Vega-Kenyon dan Schoenebeck-Trevisan-Tulsiani), tetapi Goemans Algoritma -Williamson SDP memiliki perkiraan .878 ...

$\Omega(\log n)$ $O(\sqrt{\log n})$

Mungkin kurang dikenal, Karloff dan Zwick menunjukkan bahwa menggunakan SDP seseorang dapat mendekati Max 3SAT, dalam versi di mana klausa dapat memiliki 1, 2 atau 3 literal, dalam 7/8, sementara Goemans dan Williamson telah mempelajari relaksasi pemrograman linear yang mereka gunakan. digunakan untuk membuktikan perkiraan 3/4 (Yannakakis telah memberikan perkiraan 3/4 lebih awal dengan metode lain), dan relaksasi LP Goemans-Williamson dari Max 3SAT mudah terlihat memiliki celah integral 3/4.

Luca Trevisan
sumber

Ada juga hasil oleh Grant untuk menyelesaikan sistem linear di atas GF_2. Untuk sistem persamaan dengan solusi yang baik, Anda memiliki kesenjangan integral SDP (dalam bentuk yang sangat kuat) dari 2 sementara Anda dapat menggunakan Eliminasi Gaussian untuk menyelesaikan masalah dengan tepat.

YI WU
sumber