On LP-Based Approximability for Strict CSPs.
Amit KumarRajsekar ManokaranMadhur TulsianiNisheeth K. VishnoiPublished in: SODA (2011)
Keyphrases
- constraint propagation
- constraint satisfaction problems
- linear programming
- arc consistency
- constraint satisfaction
- approximation algorithms
- linear program
- search space
- non binary
- hypertree decomposition
- symmetry breaking
- np hard
- constraint networks
- sat problem
- np complete
- tree decomposition
- constraint problems
- sat encodings
- configuration problems
- solving constraint satisfaction problems
- partial constraint satisfaction
- optimal solution
- primal dual
- feasible solution
- decision diagrams
- special case