Polynomial time approximation schemes for dense instances of minimum constraint satisfaction.
Cristina BazganWenceslas Fernandez de la VegaMarek KarpinskiPublished in: Random Struct. Algorithms (2003)
Keyphrases
- constraint satisfaction
- approximation schemes
- approximation algorithms
- constraint satisfaction problems
- backtrack search
- phase transition
- special case
- np hard
- heuristic search
- combinatorial problems
- constraint propagation
- constraint programming
- worst case
- randomly generated
- soft constraints
- random instances
- russian doll search
- backtracking search
- arc consistency
- constraint solving
- constraint relaxation
- numerical methods
- product configuration
- search strategies
- computational complexity
- constraint networks
- bin packing
- binary csps
- differential equations
- state space
- robust fault detection