% max cut relaxation
close all
clear all

n = 50; % number of vertices in the graph
p = 0.4; % probability of an edge

% generate graph
W = zeros(n);
for k1 = 1:n-1
    for k2 = k1+1:n
        if rand < p
            W(k1,k2) = 1;
            W(k2,k1) = 1;
        end
    end
end

% plot graph
figure
hold on
phi = (1:n)*2*pi/n;
plot(cos(phi),sin(phi),'k.')
for k1 = 1:n-1
    for k2 = k1+1:n
        if W(k1,k2)
            plot(cos(phi([k1 k2])),sin(phi([k1 k2])),'k')
        end
    end
end
axis([-1.1 1.1 -1.1 1.1])

% solve semi-definite relaxation
cvx_begin
    variable X(n,n) semidefinite
    diag(X) == 1
    maximize(1/4*trace(W*(1 - X)))
cvx_end
upper_bound = cvx_optval;
title(['Upper bound = ',num2str(upper_bound)])