Źródło edukacyjne lub ankieta na temat analizy programu półfinałowego?

22

Podczas projektowania algorytmów aproksymacyjnych czasami rozwiązuje się program półfinałowy, po którym następuje etap zaokrąglania. Często ilustrowanym przykładem jest Max-Cut. (Zobacz np. Algorytmy aproksymacji Vijay Vazirani.)

Czy istnieją dobre źródła edukacyjne lub ankiety wykraczające poza problem Max-Cut w celu wyjaśnienia bardziej złożonych algorytmów zaokrąglania i technik wykorzystywanych do ich analizy? Mam na myśli przypadki, w których wektory rozwiązania SDP nie są rozmieszczone równomiernie na hipersferze, mają różne długości lub mają inne właściwości utrudniające analizę.

ds.algorithms reference-request approximation-algorithms semidefinite-programming csp Michał
źródło
8
Myślę, że nie otrzymujesz żadnych odpowiedzi, ponieważ tak naprawdę nie ma dobrych ankiet na temat zaokrąglania SDP :) Sanjeev Arora przeprowadził ankietę na ten temat w różnych miejscach; jego slajdy są tutaj, a linki do kilku przydatnych odniesień są tutaj . Lovasz napisał ogólną ankietę na temat programowania półfinałowego i optymalizacji kombinatorycznej, ale nie koncentruje się on na algorytmach aproksymacyjnych.
arnab
1
Dzięki Arnab. Myślę, że nigdy nie boli zapytać. :) A jeśli wokół jest wystarczające zainteresowanie, może warto pomyśleć o napisaniu czegoś ankietowego.
Michael
4
Przepraszam, moje linki zostały zniekształcone powyżej. Pierwszy link prowadził do pikomat.mff.cuni.cz/honza/napio/arora.pdf, a drugi do homepages.cwi.nl/~monique/ow-seminar-sdp, a trzeci do cs.elte.hu/~lovasz /semidef.ps
arnab
Dodano nagrodę +50, aby sprawdzić, czy są jakieś aktualizacje (lub osoby, które zaczęły pisać ankiety), odkąd pierwotnie opublikowałem pytanie.
Michael
2
Jasne, to nie jest ankieta, ale bardzo podobał mi się ten kurs Sanjeeva Arory
Alex Golovnev

Odpowiedzi:

7

Sprawdź rozdział 6 w książce „The Design of Approximation Algorytmy” autorstwa Williamsona i Shmoysa. Książka jest dostępna on-line tutaj: http://www.designofapproxalgs.com/

slimton
źródło
Dzięki. Jeśli dobrze pamiętam, książka nie wykracza daleko poza to, co już napisano w książce Vijay Vazirani w odniesieniu do SDP. Jednak rozdziały 6.4 i 6.5 oferują wgląd w bardziej zaawansowane algorytmy zaokrąglania hiperpłaszczyzny; jednak traktuje tylko (standardowy) jednolity przypadek.
Michael