Opening Solving the Max-Cut SDP
Solving the Max-Cut SDP
- Length
- 16 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Positive semidefinite matrices
The semidefinite programming relaxation of Max-Cut can be solved in polynomial time with the ellipsoid algorithm. O'Donnell starts from the definition of a positive semidefinite matrix: a symmetric with for every real vector , an infinite family of linear inequalities. A separation oracle handles that family by computing a Cholesky decomposition and checking the diagonal entries for non-negativity. The same factorization shows a symmetric matrix is PSD exactly when , so its entries are inner products . Lecture 19c of the Carnegie Mellon graduate course CS Theory Toolkit assumes linear algebra, Gaussian elimination, and prior exposure to linear programming and the ellipsoid method.

Your comment is kept while you sign up.Sign in
O'Donnell builds a PSD separation oracle from Cholesky factorization, so the ellipsoid method solves the Max-Cut SDP.
The semidefinite programming relaxation of Max-Cut can be solved in polynomial time with the ellipsoid algorithm. O'Donnell starts from the definition of a positive semidefinite matrix: a symmetric with for every real vector , an infinite family of linear inequalities. A separation oracle handles that family by computing a Cholesky decomposition and checking the diagonal entries for non-negativity. The same factorization shows a symmetric matrix is PSD exactly when , so its entries are inner products . Lecture 19c of the Carnegie Mellon graduate course CS Theory Toolkit assumes linear algebra, Gaussian elimination, and prior exposure to linear programming and the ellipsoid method.
This lecture
Lecture 62 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.