2011/10/05 by Prasad Raghavendra, Ning Tan, Raghavendra, Prasad +1 · 9 citations
Computer Science · #Advanced Graph Theory Research #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Methods in Verification
paper · pdf · doi:10.48550/arxiv.1110.1064
openalex publication_date 2011/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ∪ S = V that maximizes the numberof crossing edges, |E(S, 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(npoly(1/ε)) that given an instance of \maxbisection with value 1-ε, finds a bisection with value 1-O(√ε). 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. \citeRaghavendra08