Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING
Philip N. Klein, Hsueh-I Lu · 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, interiorpoint ), though polynomial-time, is quite expensive.We show how they can be approximately solved in ~(nm) time for graphs with n nodes and m edges.