Derandomizing Semidefinite Programming Based Approximation Algorithms

Remarkable breakthroughs have been made recently in obtaining approximate solutions to some fundamental NP-Complete problems, namely Max-Cut, Max k-Cut, Max-Sat, Max-Dicut, Max-Bisection, k Vertex Coloring, Independent Set, etc. These breakthroughs all involve polynomial time randomized algorithms based upon semidefinite programming, a technique pioneered by M. Goemans and D. Williamson (1994). In this paper, we give techniques to derandomize the above class of randomized algorithms, thus obtaining polynomial time deterministic algorithms with the same approximation ratios for the above problems. Note that Goemans and Williamson also gave an elegant method to derandomize their Max-Cut algorithm. We show here that their technique has a fatal flaw. The techniques we subsequently develop are very different from theirs. At the heart of our technique is the use of spherical symmetry to convert a nested sequence of n integrations, which cannot be approximated sufficiently well in polynomial time, to a nested sequence of just a constant number of integrations, which can be approximated sufficiently well in polynomial time.

Authors

• Sanjeev Mahajan
• Ramesh Hariharan

Keywords

• Approximation algorithms
• Polynomials
• NP-complete problem
• Plasma welding
• Heart
• Organizing
• Estimation Algorithm
• Semidefinite Programming
• Independent Set
• Approximate Ratio
• Normal Distribution
• Discretion
• Unidimensional
• Conditional Probability
• Hyperplane
• Random Vector
• Algorithm For Problem
• Time Error
• N-dimensional Space
• Spherically Symmetric
• N-vector