On Quadratic Threshold CSPs
Per Austrin, Siavosh Benabbas, Avner Magen
Abstract
A predicate P: {-1, 1}k
→{0, 1} can be associated with a constraint
satisfaction problem Max
CSP(P). P is called ``approximation
resistant'' if Max CSP(P) cannot be
approximated better than the approximation obtained by choosing a
random assignment, and ``approximable'' otherwise. This classification
of predicates has proved to be an important and challenging open
problem. Motivated by a recent result of Austrin and Mossel
(Computational Complexity, 2009), we consider a natural subclass of
predicates defined by signs of quadratic polynomials, including the
special case of predicates defined by signs of linear forms, and
supply algorithms to approximate them as follows. In the quadratic
case we prove that every symmetric predicate is
approximable. We introduce a new rounding algorithm for the standard
semidefinite programming relaxation of Max
CSP(P) for any predicate P: {-1,
1}k →{0, 1} and analyze
its approximation ratio. Our rounding scheme operates by first
manipulating the optimal SDP solution so that all the vectors are
nearly perpendicular and then applying a form of hyperplane rounding
to obtain an integral solution. The advantage of this method is that
we are able to analyze the behaviour of a set of k
rounded variables together as opposed to just a pair of rounded
variables in most previous methods. In the linear case we prove that a
predicate called ``Monarchy'' is approximable. This predicate is not
amenable to our algorithm for the quadratic case, nor to other
LP/SDP-based approaches we are aware of.
Full Text: PDF PostScript