Fonte educacional ou pesquisa sobre análise do programa semidefinido?

22

Ao projetar algoritmos de aproximação, às vezes se resolve um programa semidefinido seguido de uma etapa de arredondamento. Um exemplo frequentemente usado para ilustrar isso é o Max-Cut. (Veja, por exemplo, Algoritmos de Aproximação de Vijay Vazirani.)

Existem boas fontes educacionais ou pesquisas que vão além do problema Max-Cut para explicar algoritmos e técnicas de arredondamento mais complexos usados ​​em suas análises? Estou pensando em casos em que os vetores da solução SDP não são distribuídos uniformemente em uma hiperesfera, têm comprimentos diferentes ou outras propriedades que dificultam a análise.

ds.algorithms reference-request approximation-algorithms semidefinite-programming csp Michael
fonte
8
Acho que você não está obtendo respostas, porque realmente não existem boas pesquisas para contornar os SDPs :) Sanjeev Arora fez uma palestra sobre o assunto em vários lugares; seus slides estão aqui e links para várias referências úteis estão aqui . Lovasz escreveu uma pesquisa geral sobre programação semidefinida e otimização combinatória, mas isso não está focado em algoritmos de aproximação.
arnab
1
Obrigado Arnab. Eu acho que nunca é demais perguntar. :) E se houver interesse suficiente por perto, talvez alguém possa pensar em escrever alguma pesquisa.
Michael
4
Desculpe, meus links foram destruídos acima. O primeiro link foi para pikomat.mff.cuni.cz/honza/napio/arora.pdf e o segundo para homepages.cwi.nl/~monique/ow-seminar-sdp e o terceiro para cs.elte.hu/~lovasz /semidef.ps
arnab
Adicionada uma recompensa de +50 para ver se há atualizações (ou pessoas que começaram a escrever pesquisas) desde que eu postei a pergunta originalmente.
Michael
2
Claro, não é uma pesquisa, mas gostei muito deste curso de Sanjeev Arora: mpi-inf.mpg.de/conference/adfocs/material/… #
Alex Golovnev

Respostas:

7

Veja o capítulo 6 do livro "The Design of Approximation Algorithms" de Williamson e Shmoys. O livro está disponível on-line aqui: http://www.designofapproxalgs.com/

Slimton
fonte
Obrigado. Se bem me lembro, o livro não vai muito além do que já está escrito no livro de Vijay Vazirani em relação aos SDPs. No entanto, os capítulos 6.4 e 6.5 oferecem informações sobre algoritmos de arredondamento hiperplano mais avançados; no entanto, trata apenas o estojo uniforme (padrão).
Michael