Tech Report CS-96-33

Efficient Approximation Algorithms for Some Semidefinite Programs

Hsueh-I Lu

December 1996

Abstract:

Linear programming has been fruitful in designing approximation algorithms for many combinatorial optimization problems. Nonlinear programming did not receive as much attention in this respect until the recent work by Goemans and Williamson. They use {\em semidefinite programs} to obtain approximation solutions with much better approximation factors. For example, the best previously known approximation algorithm for MAXCUT, which was invented twenty years ago, has approximation factor 0.5. The algorithm of Goemans and Williamson dramatically improves the approximation factor to 0.878. Inspired by the work on MAXCUT, Karger, Motwani, and Sudan adapt the same technique and obtain the currently best approximation algorithm for coloring a $k$-colorable graph with the fewest possible number of colors. The approximation ratio is improved by a factor of $\Omega(n^{2/k})$ over the best previously known result. Besides MAXCUT and COLORING, the technique of semidefinite programming has been successful in designing approximation algorithms for many other optimization problems. Each of these improved algorithms is based on obtaining a near-optimal solution to a semidefinite program, which is referred as the {\em semidefinite relaxation} of the underlining optimization problem. Therefore how to approximately solve these semidefinite relaxations efficiently, in both time and space, is practically important. All the previous work resorts to {\em interior-point methods} for this step. In the thesis the framework of Plotkin, Shmoys, and Tardos is adapted to obtain near-optimal solutions to the semidefinite relaxations of MAXCUT and COLORING. The results significantly reduce the work space required by the best known approximation algorithms for MAXCUT and COLORING if the given graph is sparse. As a consequence, the results in the thesis enable the best known approximation algorithms for MAXCUT and COLORING to work on much larger sparse graphs than they did with interior-point methods.

(complete text in pdf or gzipped postscript)