Approximate Constraint Satisfaction Requires Large LP Relaxations.
Siu On ChanJames R. LeePrasad RaghavendraDavid SteurerPublished in: J. ACM (2016)
Keyphrases
- constraint satisfaction
- constraint satisfaction problems
- lp relaxation
- constraint propagation
- heuristic search
- constraint programming
- linear programming
- russian doll search
- message passing
- phase transition
- soft constraints
- robust fault detection
- constraint relaxation
- integer programming
- sat solvers
- global constraints
- combinatorial problems
- exact solution
- special case