Relaksasi SDP set independen

Saya sedang melihat halaman 28 Lovasz "Program semidefinit dan optimasi kombinatorial" dan ini memberikan perkiraan berikut tentang angka kemandirian grafik

max u^{'} Z u

$\max u' Z u$

Z ≻ 0

$Z\succ 0$

Z_{i j} = 0 \forall i j \in E (G)

$Z_{ij}=0 \ \forall ij\in E(G)$

t r (Z) = 1

$tr(Z)=1$

Bisakah saya mendapatkan set independen (atau sesuatu yang dekat dengan set independen) langsung dari solusi relaksasi SDP? Lovasz mengatakan bahwa SDP adalah satu-satunya cara yang diketahui untuk menyelesaikan masalah ini persis untuk grafik sempurna, apakah itu masih benar?

Klarifikasi: ada relaksasi SDP serupa untuk ukuran potongan maksimum, dan saya bisa mendapatkan solusi lengkap (potongan sebenarnya, bukan ukurannya) dengan mengambil akar kuadrat dari Z dan melakukan pembulatan acak (Bab 6 buku Williamson / Shmoys) ). Saya ingin tahu apakah ada teknik serupa untuk masalah ini

ds.algorithms graph-theory semidefinite-programming independent-set Yaroslav Bulatov
sumber

Untuk pertanyaan pertama, saya tidak benar-benar mengerti apa yang Anda maksud dengan "set independen aktual". SDP adalah relaksasi, sehingga nilai optimal SDP membatasi angka independensi dari atas. Jika mereka berbeda, tidak ada set independen yang mencapai nilai optimal SDP. Ini dapat terjadi jika grafiknya tidak sempurna. Bisakah Anda membuatnya lebih eksplisit apa yang Anda butuhkan untuk "set independen aktual" Anda?

Yoshio Okamoto

Saya ingin mendapatkan perangkat independen terbesar daripada "ukuran perangkat independen terbesar"

Yaroslav Bulatov

Terima kasih atas klarifikasi, tapi saya masih bertanya-tanya. SDP untuk pemotongan maksimum digunakan untuk perkiraan. Yaitu, pembulatan acak memberikan potongan yang memiliki nilai "dekat" dengan nilai potong optimal, tidak harus potongan maksimum nyata. Jika Anda memerlukan teknik serupa, saya kira yang Anda inginkan adalah perangkat independen yang memiliki ukuran mendekati angka independensi. Atau, apakah Anda berkonsentrasi pada grafik sempurna, atau ingin berurusan dengan grafik umum?

Yoshio Okamoto

Saya ingin menemukan Set Independen Maksimum dalam Grafik Sempurna. ipsofacto memberikan solusi, tetapi membutuhkan penyelesaian beberapa SDP

Yaroslav Bulatov

Jawaban:

Saya percaya SDP adalah satu-satunya teknik yang dikenal untuk memecahkan masalah set independen maksimum pada grafik sempurna. Untuk mendapatkan set independen, seseorang dapat melakukan hal berikut. Tebak jika sebuah vertex berada di set independen, hapuslah dan selesaikan SDP. Jika mengembalikan nilai yang sama, maka ada set independen tanpa simpul ini. Jadi, buat simpul ini berdekatan dengan semua simpul lainnya, dan lanjutkan. Ini akan memberi Anda set independen yang sebenarnya.

Jika tidak, kami telah mengidentifikasi satu simpul dari set independen, dan kami dapat menghapusnya dan melanjutkan pada grafik yang tersisa.

ipsofacto
sumber

Selain itu, ini telah diterapkan dan berfungsi dengan baik (dengan beberapa optimisasi): E. Alper Yıldırım dan Xiaofei Fan-Orzechowski, Pada Ekstraksi Set Stabil Maksimum dalam Grafik Sempurna Menggunakan Fungsi Theta Lovász , Optimalisasi Komputasi dan Aplikasi 33 , 229-2424, 2006 . dx.doi.org/10.1007/s10589-005-3060-5

András Salamon

Menarik ... tampaknya kesempurnaan tidak diperlukan untuk memperkirakan angka kemandirian SDP secara tepat (berikut ini adalah mathoverflow.net/questions/57336/… ), jadi ini harus bekerja untuk kelas grafik yang lebih besar

Yaroslav Bulatov

@Yaroslav: Anda benar, kesempurnaan tidak diperlukan. Tetapi jika Anda mengadaptasi strategi ipsofacto yang disarankan, Anda akan perlu penghapusan simpul juga memiliki properti yang sama. Kondisi ini terpenuhi secara otomatis jika grafiknya sempurna, tetapi sebaliknya Anda harus berhati-hati.

Yoshio Okamoto

Saya tidak yakin apakah komentar Lovasz masih berlaku. Ada beberapa pekerjaan terbaru tentang masalah ini (dan terkait) pada grafik sempurna. Anda harus melihat pada tautan berikut untuk teknik yang melibatkan pengiriman pesan daripada menyelesaikan SDP: http://www.cs.columbia.edu/~jebara/papers/uai09perfect.pdf

Nicholas Ruozzi
sumber

Makalah yang menarik, apakah saya memahaminya dengan benar bahwa jika produk-max menyatu pada grafik yang sempurna, maka decoding rakus akan memulihkan set independen maksimum?

Yaroslav Bulatov

Saya telah membaca skim kertas, tetapi saya tidak dapat menemukan bagaimana metode memecahkan masalah set independen maksimum untuk grafik sempurna dalam waktu polinomial. Jumlah klik maksimal dapat eksponensial dalam grafik yang sempurna, sehingga waktu berjalan dalam Corollaries 1 dan 2 bukan polinomial. Meskipun saya tidak terlalu memahami isi Bagian 7, saya tidak melihat masalah optimasi linier mana yang diselesaikan dalam Bagian 7. Eksperimen dilakukan untuk masalah pencocokan maksimum, tetapi tidak untuk masalah set independen maksimum.

Yoshio Okamoto

@yoshio Anda benar. LP untuk MWIS dikenal sebagai integral jika Anda memasukkan kendala yang sesuai untuk semua (banyak eksponensial) klik. Dan itu adalah kesempurnaan dari grafik klik yang dibahas oleh makalah ini. Sepertinya penulis hanya menduga bahwa produk-maksimal pada NMRF selalu menghasilkan penugasan MAP yang benar.

Nicholas Ruozzi

Terima kasih. Lalu, dapatkah saya berasumsi bahwa makalah ini tidak memberikan algoritma waktu polinomial untuk masalah set independen maksimum untuk grafik sempurna?

Yoshio Okamoto

@YoshioOkamoto: sepertinya begitu. Makalah baru-baru ini memberikan contoh grafik yang sempurna di mana pendekatan ini konvergen ke solusi yang salah. Gambar 3 dari "Meninjau Kembali Perkiraan MAP, Passing Pesan dan Grafik Sempurna" ( datalab.uci.edu/papers/AISTATS_perfect_graphs.pdf )

Yaroslav Bulatov