A new way to use semidefinite programming with applications to linear equations mod p
Gunnar B.J. Andersson, Lars Fredrik Engebretsen, Johan Håstad · 1999
. We introduce a new method to construct approximation algorithms for combinatorial optimization problems using semidefinite programming. It consists of expressing each combinatorial object in the original problem as a constellation of vectors in the semidefinite program. When we apply this technique to systems of linear equations mod p with at most two variables in each equation, we can show that the problem is approximable within (1 - #(p))p, where #(p) > 0 for all p. Using standard techniques, we also show that it is NP-hard to approximate the problem within a constant ratio, independent of p. 1 Introduction Several combinatorial maximization problems have the following property: The naive algorithm which simply chooses a solution at random from the solution space is guaranteed to give a solution of expected weight at least some constant times the weight of the optimal solution. For instance, applying the above randomized algorithm to Max Cut yields a solution with expected weigh...