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.
ds.algorithms
reference-request
approximation-algorithms
semidefinite-programming
csp
Michael
la source
la source
Réponses:
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/
la source
Il y a un beau livre de Gartner et Matousek sur les SDP et leurs applications aux algorithmes d'approximation. Il couvre beaucoup de choses avec l'avantage supplémentaire de donner une bonne introduction à la théorie de la programmation semi-définie. Voir http://books.google.com/books/about/Approximation_Algorithms_and_Semidefinit.html?id=5QeLPOvIpNUC
la source
Il y a cette enquête: http://ttic.uchicago.edu/~madhurt/Papers/sdpchapter.pdf qui met l'accent sur les hiérarchies de la programmation convexe. Il a Max-Cut, Sparsest-Cut, coloration, ensemble indépendant d'hypergraphe, sac à dos.
la source