Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems.
Yuichi YoshidaYuan ZhouPublished in: ITCS (2014)
Keyphrases
- constraint satisfaction problems
- approximation schemes
- constraint satisfaction
- approximation algorithms
- np hard
- constraint propagation
- search space
- np complete
- numerical methods
- constraint programming
- arc consistency
- combinatorial problems
- constraint solving
- non binary
- pseudo boolean optimization
- solving constraint satisfaction problems
- decomposition methods
- soft constraints
- sat problem
- lower bound
- constraint networks
- bin packing
- constraint solver
- forward checking
- upper bound
- configuration problems
- linear programming
- partial constraint satisfaction
- heuristic search