Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs.
Johan HåstadPublished in: FOCS (2018)
Keyphrases
- constraint satisfaction problems
- constraint satisfaction
- decision diagrams
- maintaining arc consistency
- arc consistency
- real valued
- constraint propagation
- boolean functions
- ordering heuristics
- boolean queries
- search space
- constraint programming
- data sets
- tree decomposition
- non binary
- backtracking algorithm
- boolean logic
- solving constraint satisfaction problems