Source éducative ou enquête sur l'analyse du programme semi-défini?

22

Lors de la conception d'algorithmes d'approximation, on résout parfois un programme semi-fini suivi d'une étape d'arrondi. Un exemple souvent utilisé pour illustrer cela est Max-Cut. (Voir par exemple les algorithmes d'approximation de Vijay Vazirani.)

Existe-t-il de bonnes sources ou enquêtes pédagogiques allant au-delà du problème Max-Cut pour expliquer des algorithmes d'arrondi plus complexes et des techniques utilisées pour leur analyse? Je pense aux cas où les vecteurs de la solution SDP ne sont pas distribués uniformément sur une hypersphère, ils ont des longueurs différentes ou ont d'autres propriétés rendant l'analyse plus difficile.

Michael
la source
8
Je pense que vous n'obtenez pas de réponses, car il n'y a vraiment pas de bonnes enquêtes sur l'arrondissement des SDP :) Sanjeev Arora a donné une conférence sur le sujet à divers endroits; ses diapositives sont ici et des liens vers plusieurs références utiles sont ici . Lovasz a écrit une étude générale de la programmation semi-définie et de l'optimisation combinatoire, mais elle ne se concentre pas sur les algorithmes d'approximation.
arnab
1
Merci Arnab. Je suppose que ça ne fait jamais de mal de demander. :) Et s'il y a suffisamment d'intérêt autour, peut-être que l'on pourrait penser à écrire quelque chose d'enquête.
Michael
4
Désolé, mes liens ont été modifiés ci-dessus. Le premier lien était vers pikomat.mff.cuni.cz/honza/napio/arora.pdf et le second vers homepages.cwi.nl/~monique/ow-seminar-sdp et le troisième vers cs.elte.hu/~lovasz /semidef.ps
arnab
Ajout d'une prime de +50 pour voir s'il y a des mises à jour (ou des personnes qui ont commencé à rédiger des sondages) depuis que j'ai posté la question à l'origine.
Michael
2
Bien sûr, ce n'est pas une enquête, mais j'ai beaucoup aimé ce cours de Sanjeev Arora: mpi-inf.mpg.de/conference/adfocs/material/…
Alex Golovnev

Réponses:

7

Consultez le chapitre 6 du livre "The Design of Approximation Algorithms" de Williamson et Shmoys. Le livre est disponible en ligne ici: http://www.designofapproxalgs.com/

slimton
la source
Merci. Si je me souviens bien, le livre ne va pas bien au-delà de ce qui est déjà écrit dans le livre de Vijay Vazirani concernant les SDP. Cependant, les chapitres 6.4 et 6.5 offrent un aperçu des algorithmes d'arrondi hyperplan plus avancés; cependant, il ne traite que le cas uniforme (standard).
Michael