Pliability and approximating max-CSPs

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...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Romero, M, Wrochna, M, Zivny, S
Fformat:	Journal article
Iaith:	English
Cyhoeddwyd:	Association for Computing Machinery 2023

Eitemau Tebyg

Treewidth-pliability and PTAS for Max-CSPs
gan: Romero, M, et al.
Cyhoeddwyd: (2021)

Point-width and Max-CSPs
gan: Carbonnel, C, et al.
Cyhoeddwyd: (2020)

Point-width and max-CSPs
gan: Carbonnel, C, et al.
Cyhoeddwyd: (2019)

PTAS for sparse general-valued CSPs
gan: Mezei, B, et al.
Cyhoeddwyd: (2023)

PTAS for sparse general-valued CSPs
gan: Mezei, BF, et al.
Cyhoeddwyd: (2021)

Sparsification of binary CSPs
gan: Butti, S, et al.
Cyhoeddwyd: (2020)

Sparsification of Binary CSPs
gan: Butti, S, et al.
Cyhoeddwyd: (2019)

Additive sparsification of CSPs
gan: Pelleg, E, et al.
Cyhoeddwyd: (2023)

Additive sparsification of CSPs
gan: Pelleg, E, et al.
Cyhoeddwyd: (2021)

On planar valued CSPs
gan: Fulla, P, et al.
Cyhoeddwyd: (2016)

On planar valued CSPs
gan: Fulla, P, et al.
Cyhoeddwyd: (2017)

The complexity of finite-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2016)

The complexity of conservative valued CSPs
gan: Kolmogorov, V, et al.
Cyhoeddwyd: (2012)

The complexity of conservative valued CSPs
gan: Kolmogorov, V, et al.
Cyhoeddwyd: (2011)

The complexity of conservative valued CSPs
gan: Kolmogorov, V, et al.
Cyhoeddwyd: (2013)

The Complexity of Finite-Valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2013)

The complexity of finite-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2013)

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
gan: Backens, M, et al.
Cyhoeddwyd: (2019)

The complexity of general-valued CSPs seen from the other side
gan: Carbonnel, C, et al.
Cyhoeddwyd: (2018)

The complexity of conservative finite-valued CSPs
gan: Kolmogorov, V, et al.
Cyhoeddwyd: (2010)

Sherali-Adams relaxations for valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2015)

The Power of Linear Programming for Valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2012)

The power of linear programming for valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2015)

The power of linear programming for valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2012)

Necessary conditions for tractability of valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2015)

On Approximability of Satisfiable k-CSPs: II
gan: Bhangale, Amey, et al.
Cyhoeddwyd: (2023)

On Approximability of Satisfiable k-CSPs: III
gan: Bhangale, Amey, et al.
Cyhoeddwyd: (2023)

CLAP: A new algorithm for promise CSPs
gan: Ciardo, L, et al.
Cyhoeddwyd: (2023)

On approximability of satisfiable k -CSPs: I
gan: Bhangale, Amey, et al.
Cyhoeddwyd: (2022)

The complexity of Boolean surjective general-valued CSPs
gan: Fulla, P, et al.
Cyhoeddwyd: (2017)

The limits of SDP relaxations for general-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2018)

The complexity of Boolean surjective general-valued CSPs
gan: Fulla, P, et al.
Cyhoeddwyd: (2017)

The limits of SDP relaxations for general-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2017)

The complexity of Boolean surjective general-valued CSPs
gan: Fulla, P, et al.
Cyhoeddwyd: (2018)

The power of Sherali-Adams relaxations for general-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2015)

The power of Sherali-Adams relaxations for general-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2017)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
gan: Cooper, M, et al.
Cyhoeddwyd: (2017)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
gan: Cooper, M, et al.
Cyhoeddwyd: (2016)

On singleton arc consistency for CSPs defined by monotone patterns
gan: Carbonnel, C, et al.
Cyhoeddwyd: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
gan: Carbonnel, C, et al.
Cyhoeddwyd: (2018)