Opening The Semidefinite Programming Relaxation for Max-Cut
The Semidefinite Programming Relaxation for Max-Cut
- Length
- 33 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 6: Before the lecture
The semidefinite programming relaxation for Max-Cut grows out of an integer linear program with binary variables for vertices and for cut edges. In lecture 19b of the graduate course CS Theory Toolkit at Carnegie Mellon University, O'Donnell shows why linear constraints cannot force each edge variable to equal the required product. Switching to vertex values makes the objective linear and yields a moment constraint that captures Max-Cut exactly but stays intractable. Expanding the square of a linear combination of vectors gives infinitely many valid linear inequalities, the SDP constraint traced to Delorme and Poljak around 1990. Given a separation oracle, the ellipsoid algorithm solves the resulting program efficiently, leaving a fractional solution to round.
Your comment is kept while you sign up.Sign in
Derives the Max-Cut SDP as infinitely many linear inequalities that the ellipsoid algorithm can still handle.
The semidefinite programming relaxation for Max-Cut grows out of an integer linear program with binary variables for vertices and for cut edges. In lecture 19b of the graduate course CS Theory Toolkit at Carnegie Mellon University, O'Donnell shows why linear constraints cannot force each edge variable to equal the required product. Switching to vertex values makes the objective linear and yields a moment constraint that captures Max-Cut exactly but stays intractable. Expanding the square of a linear combination of vectors gives infinitely many valid linear inequalities, the SDP constraint traced to Delorme and Poljak around 1990. Given a separation oracle, the ellipsoid algorithm solves the resulting program efficiently, leaving a fractional solution to round.
Papers by Delorme and Poljak
This lecture
Lecture 61 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.