optional · interactive figures

Explore: PSD matrices and Goemans–Williamson

A 2×2 matrix and the two vectors it describes, and the Goemans–Williamson vectors with a hyperplane you can turn.

optional: nothing in the lab depends on itback to the slides

25 · explore

A 2×2 matrix is two vectors

Try: slide the entry from −½ (120°) to −1 (opposite) and past it. Static version: PSD on 2×2 matrices.

25 · explore

Goemans–Williamson, with a hyperplane you can turn

Try: turn the hyperplane on the 5-cycle (every position cuts 4), then on the random weighted graph, where positions differ. Static version: GW on the 5-cycle.

What it shows. The SDP vectors, one per vertex, drawn in their plane; a hyperplane through the centre (drag its normal); the two sides; and which edges it cuts (green) or not (red, dashed). On the right: the SDP bound, the exact expected cut, the optimum, and a histogram of the cut weights of 2000 recorded random hyperplanes, with the expected cut and the SDP bound marked.

Odd cycles: neighbours sit far apart, every hyperplane cuts all but one edge, and the rounding always finds the optimum. The loss is all between the SDP and the integers.
A random weighted graph on 8 vertices: its optimal vectors happen to lie in a plane too, and hyperplanes now give different cuts; the average stays above 0.878 of the SDP bound.

Data: slides/viz/traces/u25.py, from the reference maxcut_sdp, vectors_from_gram, expected_cut, hyperplane_round (seeded) and gw_constant; optima by brute force. The vectors are drawn in the plane of the Gram matrix's top two eigenvectors, which holds them exactly (rank 2).