Semidefinite Relaxation

Some of the hardest problems in computer science ask you to make a collection of yes/no decisions — assign this city to cluster A or B, cut this edge or leave it, color this node red or blue. The number of candidate solutions grows exponentially, and exhaustive search quickly becomes hopeless.

Semidefinite relaxation is a surprising escape route: instead of forcing every variable to be exactly 0 or 1, you let each one become a unit vector in high-dimensional space. The resulting problem — a semidefinite program (SDP) — is convex, can be solved in polynomial time, and its optimum is an upper bound on the hard discrete problem. Then you round the vectors back into binary choices using a randomized geometric trick.

The classic showcase is the Goemans-Williamson algorithm (1995) for the Max-Cut problem. Given a graph, partition its vertices into two groups to maximize the number of edges that cross the partition. Max-Cut is NP-hard, so no one expects an exact polynomial algorithm. Goemans and Williamson showed that their SDP rounding achieves at least 0.878 (about 87.8%) of the optimal cut — a provable guarantee, not just an empirical observation.

The demo below runs a simplified Goemans-Williamson-style rounding on a small graph. Each node starts with a random unit vector in 2-D (the SDP assigns unit vectors in $n$-D; 2-D is enough to visualize the idea). A random hyperplane through the origin splits the plane, assigning every node to side A or B depending on which half-plane its vector lands in.

<!-- {{c_title_comment}} -->
<p class="hint">{{hint_para}}</p>
<div class="canvas-wrap">
  <canvas id="cv" width="320" height="220"></canvas>
</div>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btn-random" type="button">{{btn_random}}</button>
  <button id="btn-best" type="button">{{btn_best}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="legend" id="legend"></div>

/* {{c_style_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.canvas-wrap { display: flex; justify-content: center; margin: 0 0 .5rem; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f8fafc; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 14px system-ui, sans-serif; padding: .42rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.legend { font-size: .82rem; color: #555; line-height: 1.6; }
.legend span { display: inline-block; width: 10px; height: 10px;
               border-radius: 50%; margin-right: 4px; vertical-align: middle; }
.dot-a { background: #e63946; }
.dot-b { background: #457b9d; }

// Code not found

Click New random cut to draw a fresh hyperplane and see a different partition. Click Best of 20 to run 20 random cuts and keep the one with the most crossing edges — this is exactly how the Goemans-Williamson rounding works in practice. Notice how often the result matches or nearly matches the true optimum shown at the bottom.

The SDP relaxation sits at a remarkable intersection of geometry, algebra and complexity theory.

• Solving the SDP is the easy part. Semidefinite programs are convex and can be solved to any desired accuracy in polynomial time by interior-point methods. The number of variables is $O(n^{2})$ (one entry per pair of vectors), and modern solvers handle instances with thousands of nodes.
• The rounding guarantee. After solving, each node $i$ holds a unit vector $v_{i}$. A random unit vector $r$ is drawn; node $i$ goes to side A if $r \cdot v_{i} \geq 0$, else side B. For each edge $(i,j)$, the probability that it is cut equals $\frac{\theta_{ij}}{\pi}$, where $\theta_{ij}$ is the angle between $v_{i}$ and $v_{j}$. Goemans and Williamson proved that $\frac{\theta / \pi}{(1 - \cos \theta)/2} \geq 0.878$ for all $\theta \in [0, \pi]$, so the expected cut is at least $0.878$ times the SDP optimum, which is itself at least the true optimum.
• Optimality under the Unique Games Conjecture. Khot, Kindler, Mossel and O'Donnell (2007) showed that if the Unique Games Conjecture is true, then no polynomial-time algorithm can beat the 0.878 factor. The conjecture is widely believed but not proved, making 87.8% the likely-best barrier for max-cut.
• Beyond max-cut. The same toolkit powers approximation algorithms for graph coloring, constraint satisfaction, and quantum information problems. SDP hierarchies (Lasserre, Sherali-Adams+SDP) can squeeze out even better bounds by adding more rounds of relaxation.

Semidefinite relaxation is not just a theoretical curiosity — it delivers practical near-optimal solutions in many fields:

• VLSI circuit partitioning: dividing a chip's components between two halves of a board to minimize the wire crossings is essentially a max-cut problem. SDP rounding gives a proven near-optimal split.
• Community detection in networks: finding densely-connected clusters in social or biological networks can be cast as a graph-partitioning SDP, yielding provably good community structure.
• Quantum information theory: the quantum chromatic number and other quantum graph parameters are naturally expressed as SDPs. Semidefinite programming is the primary tool for bounding what quantum protocols can achieve.
• Constraint satisfaction and MAX-2-SAT: the Goemans-Williamson technique extends to SAT-style problems, giving the best known approximation ratios for many CSPs.
• Control theory and signal processing: stability analysis of dynamical systems and certain filter design problems reduce to checking feasibility of an SDP.

In all these cases the key payoff is the same: a polynomial-time algorithm with a provable worst-case guarantee, which heuristics and local search cannot match.

Semidefinite relaxation is one of the deepest ideas in the theory of algorithms: when a combinatorial problem is too hard to solve exactly, lift it into the geometry of unit vectors, solve the relaxed problem efficiently, then slice the sphere with a random hyperplane to snap everything back to a discrete answer.

The result is not just "usually good" — it comes with a mathematical guarantee. For max-cut that guarantee is 87.8%, and it is likely the best any efficient algorithm can ever achieve. That is the quiet power of the technique: it turns intractability from a wall into a precisely measured gap, and shows us exactly how close we can get to the optimal answer without breaking the bounds of polynomial time.

If you want to go further, the natural next step is the P vs NP question itself — the question that determines whether these gaps can ever be closed.