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ę.
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
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
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
Jasne, to nie jest ankieta, ale bardzo podobał mi się ten kurs Sanjeeva Arory
—
Alex Golovnev