Near-optimal algorithms for maximum constraint satisfaction problems.
Moses CharikarKonstantin MakarychevYury MakarychevPublished in: SODA (2007)
Keyphrases
- constraint satisfaction problems
- pseudo boolean optimization
- constraint satisfaction
- computational problems
- non binary
- combinatorial problems
- backtracking search
- np complete
- constraint propagation
- constraint programming
- problems in artificial intelligence
- soft constraints
- orders of magnitude
- search space
- constraint optimization
- forward checking
- decomposition methods
- worst case
- constraint problems
- reasoning problems
- constraint solver
- constraint solving
- constraint graph
- backtracking algorithm
- search algorithm
- arc consistency
- tractable subclasses