c5cut.jl

# calculate sdp approximation for C5

using Random, LinearAlgebra, JuMP, CSDP

n = 5 #number of vertices
V = 1:n
E = [(i, i+1).%n.+1 for i in V]

m = Model(CSDP.Optimizer)
X = @variable(m, X[1:n, 1:n], PSD)
@objective(m, Max, sum(1-X[i,j] for (i,j) in E)/2)
for i = V
	@constraint(m, X[i, i] == 1)
end

optimize!(m)
sdp = objective_value(m)

# cut[i] should be in {-1, 1}
w(cut) = sum(1 - cut[i]*cut[j] for (i,j) in E)/2

# Goemans-Williamson algorithm
function gwcut(X)
	C = cholesky(X).U #X = C'C
	cut = repeat([1], n)	
	while w(cut) < .878 * sdp
		# choose random unit vector on n dimensional sphere
		r = normalize(randn(n))
		cut = sign.(C'*r)
	end
	return cut
end

#compare gw cut to optimal value mc = 4
cut = gwcut(value(X))
w(cut)