The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451).
Johan HåstadAndrei A. KrokhinDániel MarxPublished in: Dagstuhl Reports (2012)
Keyphrases
- constraint satisfaction problems
- constraint satisfaction
- constraint propagation
- constraint programming
- np hard
- np complete
- arc consistency
- partial constraint satisfaction
- search space
- non binary
- constraint problems
- constraint solving
- space complexity
- soft constraints
- constraint networks
- global constraints
- approximation algorithms
- computational complexity
- sat problem
- decomposition methods
- decision problems
- tractable subclasses
- disjunctive temporal
- constraint solver
- pseudo boolean optimization
- finding optimal solutions
- finite domain
- hard constraints
- worst case
- lower bound