Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies

Understand

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.