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...
Hlavní autoři: | Romero, M, Wrochna, M, Zivny, S |
---|---|
Médium: | Journal article |
Jazyk: | English |
Vydáno: |
Association for Computing Machinery
2023
|
Podobné jednotky
-
Treewidth-pliability and PTAS for Max-CSPs
Autor: Romero, M, a další
Vydáno: (2021) -
Point-width and Max-CSPs
Autor: Carbonnel, C, a další
Vydáno: (2020) -
Point-width and max-CSPs
Autor: Carbonnel, C, a další
Vydáno: (2019) -
PTAS for sparse general-valued CSPs
Autor: Mezei, B, a další
Vydáno: (2023) -
PTAS for sparse general-valued CSPs
Autor: Mezei, BF, a další
Vydáno: (2021)