Хабрахабр (Стас Фомин)/Релаксация MAX-CUT — различия между версиями

Текущая версия на 07:38, 30 мая 2012

• Написать, для данной матрицы весов W (numpy array, например), формулировку и решение задачи векторного программирования.
• Векторное программирование свести к semidefinite и для решения использовать пакет CVXOPT.
• Для Windows сборку CVXOPT брать тут http://www.lfd.uci.edu/~gohlke/pythonlibs/#cvxopt
• Придется вкурить документацию к CVXOPT (крутой оптимизационный пакет, очень полезно).

Собственно решение релаксации будет давать верхнюю оценку для MAX-CUT.

Решения этой задачи достаточно на «отлично».