In the Goemans-Williamson MAX-CUT algorithm, each vertex i is assigned a unit vector v_i in R^n, and the SDP maximizes sum_{(i,j) in E} (1 - v_i · v_j) / 2. The rounding step picks a random hyperplane and cuts based on which side each vector falls. Why does this rounding achieve ratio ~0.878?
AThe hyperplane always cuts at least 87.8% of edges
BFor each edge (i,j), the probability the hyperplane separates v_i and v_j is arccos(v_i · v_j) / pi, and the ratio arccos(x)/(pi * (1-x)/2) is minimized at ~0.878 over x in [-1,1], giving a worst-case ratio of ~0.878 between the rounded solution and the SDP value
CThe SDP relaxation has integrality gap exactly 0.878
DThe random hyperplane is chosen to maximize the cut, not chosen randomly
The key identity: a random hyperplane through the origin separates two unit vectors v_i, v_j with probability arccos(v_i · v_j) / pi. The SDP contribution of edge (i,j) is (1 - v_i · v_j) / 2. The ratio of expected rounding benefit to SDP benefit is arccos(v_i · v_j) / (pi * (1 - v_i · v_j) / 2). This ratio depends on the angle between vectors and is minimized at approximately 0.87856 (when v_i · v_j ≈ -0.689). Since the minimum ratio holds for every edge independently, the overall expected cut is at least 0.878 * SDP_OPT >= 0.878 * OPT.
Question 2 True / False
SDP relaxations are strictly more powerful than LP relaxations: for any combinatorial optimization problem, the SDP integrality gap is at most the LP integrality gap.
TTrue
FFalse
Answer: True
Every LP can be written as an SDP (the positive semidefinite constraint reduces to nonnegative diagonal entries when the matrix is diagonal). So the SDP feasible region contains the LP feasible region, meaning the SDP relaxation is at least as tight. For many problems it is strictly tighter: the MAX-CUT LP relaxation has integrality gap 1/2 (every LP solution can be rounded to a cut of half the edges), while the SDP integrality gap is ~0.878. This extra power comes from the ability to capture pairwise correlations between variables through the matrix structure, which LP's linear constraints cannot express.
Question 3 Short Answer
Explain the connection between the Unique Games Conjecture and the optimality of the Goemans-Williamson MAX-CUT algorithm.
Think about your answer, then reveal below.
Model answer: The Unique Games Conjecture (UGC), proposed by Khot in 2002, states that for every epsilon > 0 it is NP-hard to determine whether a unique-label constraint satisfaction problem has a solution satisfying 1-epsilon or at most epsilon of constraints. Khot, Kindler, Mossel, and O'Donnell (2007) proved that assuming the UGC, it is NP-hard to approximate MAX-CUT better than the Goemans-Williamson ratio of ~0.878. This means the SDP relaxation + hyperplane rounding is an OPTIMAL polynomial-time algorithm for MAX-CUT (assuming UGC and P != NP). More broadly, the UGC predicts that for many CSPs, the SDP integrality gap exactly characterizes the best achievable approximation ratio — making SDP relaxations the 'right' tool for these problems.
The UGC remains unproven but has become the central conjecture in approximation algorithm theory. If true, it provides a satisfying picture: the computational difficulty of approximating a problem is captured by the algebraic difficulty of rounding its SDP relaxation.
Question 4 True / False
SDPs can be solved exactly in polynomial time using interior point methods.
TTrue
FFalse
Answer: False
SDPs can be solved to arbitrary precision epsilon in time polynomial in the input size and log(1/epsilon) using interior point methods or the ellipsoid method — but not exactly in general (the optimal value may be irrational). For the purposes of approximation algorithms, polynomial-precision solutions suffice: the rounding step introduces much larger error than the SDP solver's precision. In practice, SDP solvers are significantly slower than LP solvers — the positive semidefinite constraint is harder to enforce than linear constraints — which motivates research into faster SDP algorithms and combinatorial alternatives that avoid solving SDPs altogether.