MAX-CUT: вероятностное округление/MAX-CUT на Matlab — различия между версиями

Текущая версия на 10:05, 21 июня 2012

% Количество вершин в графе
n = 3;
% Матрица весов
W = [0 2 3;
     2 0 1;
     3 1 0];
 
% Можно взять случайную матрицу для тестирования
% Получим симметричную разреженную матрицу, у нее 3\4 нули
% W = sprandsym(n, .5);
% W(1:n+1:n^2) = zeros(1, n);
 
% Задача SDP:
% trace(LX) -> max
% diag(X) = e
% X - positive semidefinite matrix
L = 1/4 * (diag(W * ones(n, 1)) - W);
% Преобразование матрицы к векторной форме и
% переход к задачи минимизации
c = -L(:);
% Преобразование ограничения diag(X) = e к векторному формату Ax = b
A = sparse(1:n, 1:n+1:n^2, ones(1, n), n, n^2);
b = ones(n, 1);
% Установление матрицы X размерности n в SeDumi
% в качестве положительно-полуопределенной
K.s = [n];
% Запуск SeDumi для решения задачи SDP
[X, Y, INFO] = sedumi(A, b, c, K);
 
% Преобразование столбца в матрицу
Xmatrix = X(1:n);
for i = 1:n-1
% Приставляем к матрице часть столбца
    Xmatrix = [Xmatrix X(i*n+1:(i+1)*n)];
end
 
% Разложение Холецкого
V = chol(Xmatrix);
% Случайный вектор
r = randn(1, n);
r = r/sqrt(r*r');
 
rV = r*V;
% Номера вершин, составляющих разрез (S, T)
idxS = find([1:n].*(rV >= 0))
idxT = find([1:n].*(rV < 0))