Approximate Constraint Satisfaction Requires Large LP Relaxations.
Siu On ChanJames R. LeePrasad RaghavendraDavid SteurerPublished in: FOCS (2013)
Keyphrases
- constraint satisfaction
- constraint satisfaction problems
- constraint programming
- lp relaxation
- constraint relaxation
- phase transition
- constraint propagation
- linear programming
- combinatorial problems
- exact solution
- heuristic search
- global constraints
- robust fault detection
- arc consistency
- russian doll search
- mathematical model
- sat solvers
- approximate solutions
- feasible solution
- linear program
- graphical models