Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies

Prasad Raghavendra, Ning Tan

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…