Approximation Algorithms via Semidefinite Programming

Semidefinite programming is a method for solving certain types of non-linear programs. I will descibe how Goemans and Williamson use it in their groundbreaking .878 approximation algorithm for the NP-complete MAX-CUT problem.