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...
| Հիմնական հեղինակներ: | , , |
|---|---|
| Ձևաչափ: | Journal article |
| Լեզու: | English |
| Հրապարակվել է: |
Association for Computing Machinery
2023
|