Хабрахабр (Стас Фомин)/Релаксация MAX-CUT — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
(нет различий)
|
Текущая версия на 07:38, 30 мая 2012
- Написать, для данной матрицы весов W (numpy array, например), формулировку и решение задачи векторного программирования.
- Векторное программирование свести к semidefinite и для решения использовать пакет CVXOPT.
- Для Windows сборку CVXOPT брать тут http://www.lfd.uci.edu/~gohlke/pythonlibs/#cvxopt
- Придется вкурить документацию к CVXOPT (крутой оптимизационный пакет, очень полезно).
Собственно решение релаксации будет давать верхнюю оценку для MAX-CUT.
Решения этой задачи достаточно на «отлично».