Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques

A number of recent papers on approximation algorithms have used the square roots of unity, −1 and 1 to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semidefinite programming in order to obtain near optimal solutions to these problems. In this talk, we consider using the cube roots of unity, 1, e, and e, to represent ternary decision variables for problems in combinatorial optimization. Here the natural relaxation is that of unit vectors in complex space. We use an extension of semidefinite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique to obtain near-optimal solutions to the problems. In particular, we consider the problem of maximizing the total weight of satisfied equations xu − xv ≡ c (mod 3) and inequations xu − xv ≡ c (mod 3), where xu ∈ {0, 1, 2} for all u. This problem can be used to model the MAX 3-CUT problem and a directed variant we call MAX 3-DICUT. For the general problem, we obtain a 0.79373-approximation algorithm. If the instance contains only inequations (as it does for MAX 3-CUT), we obtain a performance guarantee of 7 12 + 3 4π2 arccos 2(−1/4) ≈ 0.83601. Although quite different at first glance, our relaxation and algorithm appear to be equivalent to those of Frieze and Jerrum (1997) and de Klerk, Pasechnik, and Warners (2000) for MAX 3-CUT, and the ones of Andersson, Engebretson, and H̊astad (1999) for the general case. This talk is based on a joint result with David Williamson, to appear in [1].