goemans_williamson

iqm.applications.maxcut.goemans_williamson(max_cut_problem)

Runs the Goemans-Williamson algorithm for maxcut, returning a solution bitstring.

The Goemans-Williamson is a randomized algorithm for maxcut, with a guaranteed approximation ratio of around 0.87856. The algorithm was first described in [1].

Steps:

1. Relax the problem to a semidefinite program (SDP) with each variable represented by a multi-dimensional vector on a unit sphere.

2. Solve the SDP.

3. Generate a random hyperplane through the origin.

4. Assign the variables to 0 or 1 based on which side of the plane their multi-dimensional vector lies.

Parameters:

max_cut_problem (MaxCutInstance | Graph) – A problem instance of maxcut or a Graph.

Returns:

A bitstring solution.

Return type:

str