Bildungsquelle oder Umfrage zur Analyse des semidefiniten Programms?

22

Beim Entwerfen von Approximationsalgorithmen löst man manchmal ein semidefinites Programm, gefolgt von einem Rundungsschritt. Ein häufig verwendetes Beispiel, um dies zu veranschaulichen, ist Max-Cut. (Siehe zB Approximationsalgorithmen von Vijay Vazirani.)

Gibt es gute Bildungsquellen oder Umfragen, die über das Max-Cut-Problem hinausgehen und komplexere Rundungsalgorithmen und -techniken für ihre Analyse erklären? Ich denke an Fälle, in denen die Vektoren der SDP-Lösung nicht gleichmäßig auf einer Hypersphäre verteilt sind, unterschiedliche Längen aufweisen oder andere Eigenschaften aufweisen, die die Analyse erschweren.

Michael
quelle
8
Ich glaube, Sie bekommen keine Antworten, weil es wirklich keine guten Umfragen zum Thema SDP gibt :) Sanjeev Arora hat an verschiedenen Stellen einen Umfragevortrag zu diesem Thema gehalten; Seine Folien sind hier und Links zu verschiedenen nützlichen Referenzen sind hier . Lovasz hat eine allgemeine Übersicht über semidefinite Programmierung und kombinatorische Optimierung verfasst, die sich jedoch nicht auf Approximationsalgorithmen konzentriert.
Arnab
1
Danke Arnab. Ich denke, es tut nie weh zu fragen. :) Und wenn es genug Interesse gibt, könnte man vielleicht darüber nachdenken, eine Umfrage zu schreiben.
Michael
4
Entschuldigung, meine Links wurden oben entstellt. Der erste Link war zu pikomat.mff.cuni.cz/honza/napio/arora.pdf und der zweite zu homepages.cwi.nl/~monique/ow-seminar-sdp und der dritte zu cs.elte.hu/~lovasz /semidef.ps
arnab
+50 Kopfgeld hinzugefügt, um zu sehen, ob es Aktualisierungen gibt (oder Personen, die mit dem Schreiben von Umfragen begonnen haben), seit ich die Frage ursprünglich gepostet habe.
Michael
2
Klar, es ist keine Umfrage, aber mir hat dieser Kurs von Sanjeev Arora sehr gut gefallen: mpi-inf.mpg.de/conference/adfocs/material/…
Alex Golovnev

Antworten:

7

Lesen Sie Kapitel 6 im Buch "The Design of Approximation Algorithms" von Williamson und Shmoys. Das Buch ist online hier erhältlich: http://www.designofapproxalgs.com/

Slimton
quelle
Vielen Dank. Wenn ich mich richtig erinnere, geht das Buch nicht weit über das hinaus, was in Bezug auf SDPs bereits in Vijay Vaziranis Buch geschrieben ist. Die Kapitel 6.4 und 6.5 bieten jedoch Einblicke in fortgeschrittenere Rundungsalgorithmen für die Hyperebene. Dabei wird nur der (Standard-) Uniformfall behandelt.
Michael