CS 269S, Winter 2011: Theory Seminar
ICS 243
6 June 2011:

Speaker: Nickolaos Matsakis

Title: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming (JACM 1995)

Authors: M. Goemans and D. Williamson


This publication, currently, provides the best approximation ratio for the Maximum Cut problem, using a novel application of Semidefinite Programming on Approximation Algorithms. We, furthermore, discuss some newer applications and results of this technique. We focus only on the Maximum Cut problem.