On the power of symmetric LP and SDP relaxations

with James R. Lee, Prasad Raghavendra, Ning Tan. CCC 2014.

PDF

abstract

We study the computational power of general symmetric relaxations for combinatorial optimization problems, both in the linear programming (LP) and semidefinite programming (SDP) case. We show new connections to explicit LP and SDP relaxations, e.g., obtained from hierarchies.

Concretely, for $k<n/4$, we show that $k$-rounds of sum-of-squares / Lasserre relaxations of size $k{n\choose k}$ achieve best-possible approximation guarantees for Max CSPs among all symmetric SDP relaxations of size at most $n\choose k$. This result gives the first lower bounds for symmetric SDP relaxations of Max CSPs, and indicates that the sum-of-squares method provides the “right” SDP relaxation for this class of problems.

Moreover, for $k<n/4$, we show the existence of symmetric LP relaxations of size $O({n\choose k}k!)$ for the traveling salesman problem that achieve per instance best-possible approximation guarantees among all symmetric LP relaxations of size roughly $n\choose k$.