Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies

Details Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies

2011-10-05

arxiv.org/abs/1110.1064v1

Computer Science

Data Structures and Algorithms

Scientific paper

This work is concerned with approximating constraint satisfaction problems (CSPs) with an additional global cardinality constraints. For example, \maxcut is a boolean CSP where the input is a graph $G = (V,E)$ and the goal is to find a cut $S \cup \bar S = V$ that maximizes the numberof crossing edges, $|E(S,\bar S)|$. The \maxbisection problem is a variant of \maxcut with an additional global constraint that each side of the cut has exactly half the vertices, i.e., $|S| = |V|/2$. Several other natural optimization problems like \minbisection and approximating Graph Expansion can be formulated as CSPs with global constraints. In this work, we formulate a general approach towards approximating CSPs with global constraints using SDP hierarchies. To demonstrate the approach we present the following results: Using the Lasserre hierarchy, we present an algorithm that runs in time $O(n^{poly(1/\epsilon)})$ that given an instance of \maxbisection with value $1-\epsilon$, finds a bisection with value $1-O(\sqrt{\epsilon})$. This approximation is near-optimal (up to constant factors in $O()$) under the Unique Games Conjecture. By a computer-assisted proof, we show that the same algorithm also achieves a 0.85-approximation for \maxbisection, improving on the previous bound of 0.70 (note that it is \uniquegames hard to approximate better than a 0.878 factor). The same algorithm also yields a 0.92-approximation for \maxtwosat with cardinality constraints. For every CSP with a global cardinality constraints, we present a generic conversion from integrality gap instances for the Lasserre hierarchy to a {\it dictatorship test} whose soundness is at most integrality gap. Dictatorship testing gadgets are central to hardness results for CSPs, and a generic conversion of the above nature lies at the core of the tight Unique Games based hardness result for CSPs. \cite{Raghavendra08}

Affiliated with

Also associated with

No associations

Rating

Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-325936