Opening Goemans-Williamson Algorithm: Rounding the Max-Cut SDP
Goemans-Williamson Algorithm: Rounding the Max-Cut SDP
- Length
- 32 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 5: Semidefinite programming relaxation for max-cut
Cuts the Max-Cut SDP's unit vectors with a random hyperplane and shows each edge is cut with probability .
The Goemans-Williamson algorithm rounds the Max-Cut semidefinite program to a cut worth at least 0.878 times the maximum. O'Donnell starts by relaxing vertex labels to -dimensional unit vectors, so each edge's contribution depends on a dot product, the cosine of the angle between its endpoints. Lovász's umbrella, a three-dimensional configuration, serves as the optimal vector solution for the five-cycle. A random hyperplane through the origin then splits the vectors into two sides, and the expected cut is computed edge by edge from those angles. Comparing this with the SDP value gives the 0.878 ratio. Lecture 20a of O'Donnell's graduate CS Theory Toolkit at Carnegie Mellon, it assumes linear algebra, positive semidefinite matrices, basic probability and LP relaxations.
The Goemans-Williamson algorithm rounds the Max-Cut semidefinite program to a cut worth at least 0.878 times the maximum. O'Donnell starts by relaxing vertex labels to -dimensional unit vectors, so each edge's contribution depends on a dot product, the cosine of the angle between its endpoints. Lovász's umbrella, a three-dimensional configuration, serves as the optimal vector solution for the five-cycle. A random hyperplane through the origin then splits the vectors into two sides, and the expected cut is computed edge by edge from those angles. Comparing this with the SDP value gives the 0.878 ratio. Lecture 20a of O'Donnell's graduate CS Theory Toolkit at Carnegie Mellon, it assumes linear algebra, positive semidefinite matrices, basic probability and LP relaxations.
Goemans-Williamson 1994 paper
Goemans-Williamson 1994
This lecture
Lecture 63 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in