Sumber Pendidikan atau Survei tentang Analisis Program Semidefinite?

22

Ketika mendesain algoritma aproksimasi seseorang kadang-kadang memecahkan program semidefinite diikuti oleh langkah pembulatan. Contoh yang sering digunakan untuk menggambarkan ini adalah Max-Cut. (Lihat misalnya Algoritma Aproksimasi oleh Vijay Vazirani.)

Apakah ada sumber atau survei pendidikan yang baik melampaui masalah Max-Cut untuk menjelaskan algoritma pembulatan yang lebih kompleks dan teknik yang digunakan untuk analisis mereka? Saya sedang memikirkan kasus-kasus ketika vektor solusi-SDP tidak terdistribusi secara seragam pada hypersphere, mereka memiliki panjang yang berbeda, atau memiliki sifat lain yang membuat analisis lebih sulit.

ds.algorithms reference-request approximation-algorithms semidefinite-programming csp Michael
sumber
8
Saya pikir Anda tidak mendapatkan jawaban, karena benar-benar tidak ada survei yang baik tentang pembulatan SDP :) Sanjeev Arora telah memberikan ceramah survei tentang masalah ini di berbagai tempat; slide-nya ada di sini dan tautan ke beberapa referensi bermanfaat ada di sini . Lovasz telah menulis survei umum tentang pemrograman semidefinite dan optimasi kombinatorial, tetapi ini tidak berfokus pada algoritma aproksimasi.
arnab
1
Terima kasih Arnab. Saya kira tidak ada salahnya untuk bertanya. :) Dan jika ada cukup minat, mungkin orang bisa berpikir tentang menulis sesuatu survei.
Michael
4
Maaf, tautan saya hancur di atas. Tautan pertama adalah ke pikomat.mff.cuni.cz/honza/napio/arora.pdf dan yang kedua ke homepages.cwi.nl/~monique/ow-seminar-sdp dan yang ketiga ke cs.elte.hu/ ~lovasz /semidef.ps
arnab
Menambahkan karunia +50 untuk melihat apakah ada pembaruan (atau orang yang sudah mulai menulis survei) sejak saya memposting pertanyaan itu semula.
Michael
2
Tentu, ini bukan survei, tapi saya sangat menyukai kursus ini oleh Sanjeev Arora: mpi-inf.mpg.de/conference/adfocs/material/…
Alex Golovnev

Jawaban:

7

Periksa Bab 6 dalam buku "Desain Algoritma Aproksimasi" oleh Williamson dan Shmoys. Buku ini tersedia online di sini: http://www.designofapproxalgs.com/

Slimton
sumber
Terima kasih. Jika saya ingat dengan benar, buku itu tidak jauh melampaui apa yang sudah ditulis dalam buku Vijay Vazirani sehubungan dengan SDP. Namun, bab 6.4 dan 6.5 menawarkan wawasan tentang algoritma pembulatan pesawat yang lebih canggih; namun itu hanya menangani kasus seragam (standar).
Michael