Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction
Cristina BazganWenceslas Fernandez de la VegaMarek KarpinskiPublished in: Electron. Colloquium Comput. Complex. (2001)
Keyphrases
- constraint satisfaction
- approximation schemes
- approximation algorithms
- constraint satisfaction problems
- backtrack search
- np hard
- special case
- heuristic search
- combinatorial problems
- worst case
- constraint programming
- constraint propagation
- phase transition
- arc consistency
- randomly generated
- numerical methods
- soft constraints
- constraint relaxation
- multiscale
- russian doll search
- constraint solving
- sat solvers
- computational complexity
- propositional satisfiability
- constraint problems
- stochastic local search
- lower bound