Near-Optimal UGC-hardness of Approximating Max k-CSP_R.
Pasin ManurangsiPreetum NakkiranLuca TrevisanPublished in: CoRR (2015)
Keyphrases
- constraint satisfaction problems
- random instances
- np complete
- np hard
- ordering heuristics
- user generated content
- constraint satisfaction
- phase transition
- maintaining arc consistency
- learning theory
- tree decomposition
- randomly generated
- computational complexity
- decomposition methods
- constraint programming
- constraint propagation
- arc consistency
- sat problem
- lower bound
- hard problems
- constraint solving
- np hardness
- search space
- forward checking
- exact computation
- arc consistency algorithm
- search engine
- provably near optimal
- tree decompositions
- special case
- heuristic search
- sat instances
- global constraints