On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems.
Per AustrinRajsekar ManokaranCenny WennerPublished in: Theory Comput. (2015)
Keyphrases
- constraint satisfaction problems
- np hardness
- np hard
- constraint satisfaction
- np complete
- ordering heuristics
- approximation algorithms
- constraint propagation
- constraint programming
- scheduling problem
- search space
- lower bound
- arc consistency
- special case
- constraint solving
- optimal solution
- combinatorial problems
- non binary
- computational complexity
- global constraints
- soft constraints
- constraint networks
- decision problems
- linear programming
- backtracking search
- worst case
- pseudo boolean optimization
- linear program
- forward checking
- solving constraint satisfaction problems
- particle swarm optimization
- finding optimal solutions