Towards a Characterization of Constant-Factor Approximable Finite-Valued CSPs.

Víctor Dalmau Andrei A. Krokhin Rajsekar Manokaran

Published in: CoRR (2016)

Keyphrases

constant factor
approximation algorithms
constraint satisfaction problems
lower bound
worst case
upper bound
constraint satisfaction
arc consistency
np hard
sample complexity
search space
constraint programming
training set
simulated annealing
np complete
linear programming relaxation