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.
ds.algorithms
reference-request
approximation-algorithms
semidefinite-programming
csp
Michael
quelle
quelle
Antworten:
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/
quelle
Es gibt ein schönes Buch von Gartner und Matousek über SDPs und ihre Anwendungen auf Approximationsalgorithmen. Es deckt eine Menge ab, mit dem zusätzlichen Vorteil, eine gute Einführung in die Theorie der semidefiniten Programmierung zu geben. Siehe http://books.google.com/books/about/Approximation_Algorithms_and_Semidefinit.html?id=5QeLPOvIpNUC
quelle
Es gibt diese Umfrage: http://ttic.uchicago.edu/~madhurt/Papers/sdpchapter.pdf, die sich auf die Hierarchien der konvexen Programmierung konzentriert. Es hat Max-Cut, Sparsest-Cut, Färbung, Hypergraph Independent Set, Rucksack.
quelle