¿Fuente educativa o encuesta sobre análisis de programa semidefinido?

22

Al diseñar algoritmos de aproximación, a veces se resuelve un programa semidefinido seguido de un paso de redondeo. Un ejemplo de uso frecuente para ilustrar esto es Max-Cut. (Ver, por ejemplo, Algoritmos de aproximación de Vijay Vazirani).

¿Existen buenas fuentes educativas o encuestas que vayan más allá del problema de Max-Cut para explicar algoritmos y técnicas de redondeo más complejos utilizados para su análisis? Estoy pensando en casos en que los vectores de la solución SDP no se distribuyen uniformemente en una hiperesfera, tienen diferentes longitudes o tienen otras propiedades que dificultan el análisis.

ds.algorithms reference-request approximation-algorithms semidefinite-programming csp Miguel
fuente
8
Creo que no está obteniendo ninguna respuesta, porque realmente no hay buenas encuestas sobre el redondeo de los SDP :) Sanjeev Arora ha dado una charla sobre el tema en varios lugares; sus diapositivas están aquí y los enlaces a varias referencias útiles están aquí . Lovasz ha escrito una encuesta general de programación semidefinida y optimización combinatoria, pero esto no se centra en algoritmos de aproximación.
arnab
1
Gracias Arnab Supongo que nunca está de más preguntar. :) Y si hay suficiente interés, tal vez uno podría pensar en escribir algo topográfico.
Michael
44
Lo siento, mis enlaces fueron destrozados arriba. El primer enlace fue a pikomat.mff.cuni.cz/honza/napio/arora.pdf y el segundo a homepages.cwi.nl/~monique/ow-seminar-sdp y el tercero a cs.elte.hu/~lovasz /semidef.ps
arnab
Se agregó una recompensa de +50 para ver si hay actualizaciones (o personas que comenzaron a escribir encuestas) desde que publiqué la pregunta originalmente.
Michael
2
Claro, no es una encuesta, pero me gustó mucho este curso de Sanjeev Arora: mpi-inf.mpg.de/conference/adfocs/material/…
Alex Golovnev

Respuestas:

7

Consulte el Capítulo 6 del libro "El diseño de algoritmos de aproximación" de Williamson y Shmoys. El libro está disponible en línea aquí: http://www.designofapproxalgs.com/

Slimton
fuente
Gracias. Si no recuerdo mal, el libro no va más allá de lo que ya está escrito en el libro de Vijay Vazirani con respecto a los SDP. Sin embargo, los capítulos 6.4 y 6.5 ofrecen información sobre algoritmos de redondeo de hiperplanos más avanzados; sin embargo, solo trata el caso uniforme (estándar).
Michael