При разработке алгоритмов аппроксимации иногда решают полуопределенную программу с последующим шагом округления. Часто используемый пример, иллюстрирующий это, - Max-Cut. (См., Например, Алгоритмы аппроксимации Vijay Vazirani.)
Существуют ли хорошие образовательные источники или обзоры, выходящие за рамки проблемы Max-Cut, чтобы объяснить более сложные алгоритмы округления и методы, используемые для их анализа? Я имею в виду случаи, когда векторы решения SDP не распределены равномерно по гиперсфере, имеют разную длину или другие свойства, затрудняющие анализ.
ds.algorithms
reference-request
approximation-algorithms
semidefinite-programming
csp
Майкл
источник
источник
Ответы:
Проверьте главу 6 в книге «Разработка алгоритмов аппроксимации» Уильямсона и Шмойса. Книга доступна в Интернете здесь: http://www.designofapproxalgs.com/
источник
Есть хорошая книга Gartner и Matousek о SDP и их приложениях к алгоритмам аппроксимации. Он охватывает многое с дополнительным преимуществом, поскольку дает хорошее введение в теорию полуопределенного программирования. См. Http://books.google.com/books/about/Approximation_Algorithms_and_Semidefinit.html?id=5QeLPOvIpNUC.
источник
Вот этот обзор: http://ttic.uchicago.edu/~madhurt/Papers/sdpchapter.pdf, который фокусируется на иерархиях выпуклого программирования. Имеет Max-Cut, Sparsest-Cut, расцветку, набор для гиперграфа, рюкзак.
источник