Accepting Subcubes and the Approximability of Complete Boolean Min-CSPsResearch Paper
In a minimum constraint satisfaction problem (Min-CSP) the input is a set of Boolean variables and a list of constraints, and the goal is an assignment violating as few constraints as possible. On general instances, Min-2-CNF Deletion has an -approximation, while a constant factor would refute the Unique Games Conjecture; for Min-3-SAT any…