Maximum Cut and the Goemans–Williamson Algorithm

A paper on the Maximum Cut problem — splitting a graph’s vertices into two sides so that as many edges as possible run between them — and the Goemans–Williamson algorithm, which gets surprisingly close to the best possible cut by relaxing the problem into a semidefinite program and rounding the result at random. It is a from-scratch walkthrough of why that relaxation does so well.