Point-width and Max-CSPs

Point-width and Max-CSPs

Taispeáin leaganacha eile (1)

<p>The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs, β-acyclicity and bounded (incidence) MIM-width, are incomparable and lead to very different algorithms.</p...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Carbonnel, C, Romero, M, Živný, S
Formáid:	Journal article
Teanga:	English
Foilsithe / Cruthaithe:	Association for Computing Machinery 2020

Míreanna comhchosúla

Point-width and max-CSPs
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2019)

Pliability and approximating max-CSPs
de réir: Romero, M, et al.
Foilsithe / Cruthaithe: (2023)

Treewidth-pliability and PTAS for Max-CSPs
de réir: Romero, M, et al.
Foilsithe / Cruthaithe: (2021)

The complexity of general-valued CSPs seen from the other side
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2018)

Sparsification of binary CSPs
de réir: Butti, S, et al.
Foilsithe / Cruthaithe: (2020)

Sparsification of Binary CSPs
de réir: Butti, S, et al.
Foilsithe / Cruthaithe: (2019)

Additive sparsification of CSPs
de réir: Pelleg, E, et al.
Foilsithe / Cruthaithe: (2021)

Additive sparsification of CSPs
de réir: Pelleg, E, et al.
Foilsithe / Cruthaithe: (2023)

On planar valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2016)

On planar valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2017)

The complexity of finite-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2016)

The complexity of conservative valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2012)

The complexity of conservative valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2011)

The complexity of conservative valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2013)

The Complexity of Finite-Valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2013)

The complexity of finite-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2013)

The complexity of conservative finite-valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2010)

Sherali-Adams relaxations for valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

The Power of Linear Programming for Valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2012)

The power of linear programming for valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

The power of linear programming for valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2012)

Necessary conditions for tractability of valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

PTAS for sparse general-valued CSPs
de réir: Mezei, BF, et al.
Foilsithe / Cruthaithe: (2021)

PTAS for sparse general-valued CSPs
de réir: Mezei, B, et al.
Foilsithe / Cruthaithe: (2023)

CLAP: A new algorithm for promise CSPs
de réir: Ciardo, L, et al.
Foilsithe / Cruthaithe: (2023)

The complexity of Boolean surjective general-valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2017)

The limits of SDP relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2018)

The complexity of Boolean surjective general-valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2017)

The limits of SDP relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2017)

The complexity of Boolean surjective general-valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2018)

The power of Sherali-Adams relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

The power of Sherali-Adams relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2017)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
de réir: Cooper, M, et al.
Foilsithe / Cruthaithe: (2017)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
de réir: Cooper, M, et al.
Foilsithe / Cruthaithe: (2016)

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
de réir: Martin C. Cooper, et al.
Foilsithe / Cruthaithe: (2017-12-01)

Tractable classes of binary CSPs defined by excluded topological minors
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2015)

Small Promise CSPs that reduce to large CSPs
de réir: Alexandr Kazda, et al.
Foilsithe / Cruthaithe: (2022-08-01)

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
de réir: Backens, M, et al.
Foilsithe / Cruthaithe: (2019)