Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time.
Kun HeChunyang WangYitong YinPublished in: FOCS (2022)
Keyphrases
- constraint satisfaction
- constraint satisfaction problems
- combinatorial problems
- constraint programming
- constraint relaxation
- heuristic search
- relaxation labeling
- special case
- constraint propagation
- phase transition
- russian doll search
- probabilistic reasoning
- optimal solution
- arc consistency
- constraint networks
- backtrack search
- search strategies
- neural network
- worst case
- computational complexity
- constraint solving
- configuration problems
- np complete
- search space
- robust fault detection
- genetic algorithm