Complex Semidefinite Programming for Approximating Combinatorial Optimization Problems
by
Michel X. Goemans
Massachusetts Institute of Technology
Coauthors: David P. Williamson (IBM)

In the last few years there have been several applications of semidefinite programming to combinatorial optimization. In this talk, I will propose the use of complex semidefinite programming, i.e. the class of linear optimization problems over an affine subspace of the cone of complex positive semidefinite Hermitian matrices. In particular, I will consider the problem of maximizing the total weight of satisfied equations x_u - x_v \equiv c mod 3 and inequations x_u - x_v \not \equiv c mod 3, where x_u in { 0, 1, 2 } for all u. I will show how complex semidefinite programming can be used to derive a solution guaranteed to be within 0.79373 of the optimum in general, and within \frac 7 12 +\frac 3 4\pi²  arccos²(-1/4)  \approx 0.83601 for inequations only. This is joint work with David Williamson.

Date received: March 28, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafv-94.