Towards a Characterization of Constant-Factor Approximable Min CSPs.

Víctor Dalmau Andrei A. Krokhin Rajsekar Manokaran

Published in: SODA (2015)

Keyphrases

constant factor
approximation algorithms
lower bound
constraint satisfaction problems
upper bound
worst case
constraint satisfaction
sample complexity
constraint propagation
special case
np hard
search space
support vector machine
arc consistency