Pliability and approximating max-CSPs

We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time algorithm for an arbitrarily good approximation of the optimal value in a large class of Max-2-CSPs parameterised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Ou...

Olles dieđut

Bibliográfalaš dieđut
Váldodahkkit: Romero, M, Wrochna, M, Zivny, S
Materiálatiipa: Journal article
Giella:English
Almmustuhtton: Association for Computing Machinery 2023