0
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Aug 21, 2021 at 5:37
  • $\begingroup$ 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 $\endgroup$
    – nir shahar
    Commented Aug 21, 2021 at 12:42

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.