Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DICTATORSHIP TESTING:
Reports tagged with Dictatorship testing:
TR13-125 | 11th September 2013
Venkatesan Guruswami, Euiwoong Lee

#### Complexity of approximating CSP with Balance / Hard Constraints

We study two natural extensions of Constraint Satisfaction Problems (CSPs). {\em Balance}-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of {\em Hard}-Max-CSP consists of {\em soft constraints} and {\em hard constraints}, and the goal is to maximize ... more >>>

ISSN 1433-8092 | Imprint