Treewidth-Pliability and PTAS for Max-CSPs.
Miguel RomeroMarcin WrochnaStanislav ZivnýPublished in: SODA (2021)
Keyphrases
- search space
- constraint satisfaction problems
- constraint graph
- arc consistency
- space complexity
- maintaining arc consistency
- tree decompositions
- ordering heuristics
- constraint propagation
- constraint satisfaction
- tractable classes
- approximation algorithms
- bounded treewidth
- solving constraint satisfaction problems
- upper bound
- constraint networks
- polynomial time approximation
- np hard
- tree decomposition
- approximation schemes
- soft constraints
- np complete
- backtracking algorithm
- graph theory
- boolean functions
- symmetry breaking
- constraint programming
- hypertree decomposition
- graph model
- partial constraint satisfaction
- discrete random variables
- optimal solution
- heuristic search
- non binary
- forward checking
- search algorithm
- probabilistic reasoning
- neural network
- conjunctive queries
- bayesian networks