# Score and bound in Goemans-Williamson algorithm

I am trying to have a deeper understanding of the following implementation of the Goemans-Williamson algorithm for solving the maxcut problem.

def goemans_williamson(graph: nx.Graph) -> Tuple[np.ndarray, float, float]:
"""
The Goemans-Williamson algorithm for solving the maxcut problem.
Ref:
Goemans, M.X. and Williamson, D.P., 1995. Improved approximation
algorithms for maximum cut and satisfiability problems using
semidefinite programming. Journal of the ACM (JACM), 42(6), 1115-1145
Returns:
np.ndarray: Graph coloring (+/-1 for each node)
float:      The GW score for this cut.
float:      The GW bound from the SDP relaxation
"""
# Kudos: Originally implementation by Nick Rubin, with refactoring and
# cleanup by Jonathon Ward and Gavin E. Crooks
laplacian = np.array(0.25 * nx.laplacian_matrix(graph).todense())

# Setup and solve the GW semidefinite programming problem
psd_mat = cvx.Variable(laplacian.shape, PSD=True)
obj = cvx.Maximize(cvx.trace(laplacian * psd_mat))
constraints = [cvx.diag(psd_mat) == 1]  # unit norm
prob = cvx.Problem(obj, constraints)
prob.solve(solver=cvx.CVXOPT)

evals, evects = np.linalg.eigh(psd_mat.value)
sdp_vectors = evects.T[evals > float(1.0E-6)].T

# Bound from the SDP relaxation
bound = np.trace(laplacian @ psd_mat.value)

random_vector = np.random.randn(sdp_vectors.shape[1])
random_vector /= np.linalg.norm(random_vector)
colors = np.sign([vec @ random_vector for vec in sdp_vectors])
score = colors @ laplacian @ colors.T

return colors, score, bound


Along with the cut, it also reports score and bound.

Could anyone provide the formal definitions of score and bound for the Goemans-Williamson algorithm? TIA

• Have you read the original paper? We're not a coding site, and my understanding of our general policy is that if the question requires us to understand code to understand the question, the question is probably not suitable here. Asking us to help you understand some particular piece of code is probably out of scope here. Any community votes? Also, many people here don't read numpy.
– D.W.
Commented Aug 21, 2021 at 5:37
• I agree with @D.W. , in addition, I think its very likely those definitions exist within the original paper. From what I see here, it seems like the score is the sum of weights of edges not in the cut itself minus the sum of weights of edges that are in the cut Commented Aug 21, 2021 at 12:42