Tech Report CS-96-07

Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING

Philip N. Klein and Hsueh-I Lu

January 1996


The best known approximation algorithm for graph MAX CUT, due to Goemans and Williamson, first finds the optimal solution a semidefinite program and then derives a graph cut from that solution. Building on this result, Karger, Motwani, and Sudan gave an approximation algorithm for graph coloring that also involves solving a semidefinite program. Solving these semidefinite programs using known methods (ellipsoid, interior-point), though polynomial-time, is quite expensive. We show how they can be approximately solved in $\tilde O(nm)$ time for graphs with $n$ nodes and $m$ edges.

(complete text in pdf or gzipped postscript)