The complexity of Boolean surjective general-valued CSPs

The complexity of Boolean surjective general-valued CSPs

Show other versions (2)

<p>Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a $\overline{\mathbb{Q}}$-valued objective function given as a sum of fixed-arity functions, where $\overline{\mathbb{Q}}=\mathbb{Q}\cup\{\infty\}$ is the set of extended rationals.</p> <p>In...

Fuld beskrivelse

Bibliografiske detaljer
Main Authors:	Fulla, P, Zivny, S
Format:	Journal article
Udgivet:	2017

Lignende værker

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

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

On planar valued CSPs
af: Fulla, P, et al.
Udgivet: (2017)

On planar valued CSPs
af: Fulla, P, et al.
Udgivet: (2016)

Beyond boolean surjective VCSPs
af: Matl, G, et al.
Udgivet: (2019)

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

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

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

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

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

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

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

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

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

Using a min-cut generalisation to go beyond Boolean surjective VCSPs
af: Matl, G, et al.
Udgivet: (2020)

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

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

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

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

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

The complexity of counting surjective homomorphisms and compactions
af: Focke, J, et al.
Udgivet: (2017)

The complexity of counting surjective homomorphisms and compactions
af: Focke, J, et al.
Udgivet: (2019)

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

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

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

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

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

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

The complexity of counting locally maximal satisfying assignments of Boolean CSPs
af: Goldberg, L, et al.
Udgivet: (2016)

Conditional Dichotomy of Boolean Ordered Promise CSPs
af: Joshua Brakensiek, et al.
Udgivet: (2023-01-01)

Sparsification of binary CSPs
af: Butti, S, et al.
Udgivet: (2020)

Sparsification of Binary CSPs
af: Butti, S, et al.
Udgivet: (2019)

Additive sparsification of CSPs
af: Pelleg, E, et al.
Udgivet: (2021)

Additive sparsification of CSPs
af: Pelleg, E, et al.
Udgivet: (2023)

Expected number of locally maximal solutions for random Boolean CSPs
af: Nadia Creignou, et al.
Udgivet: (2007-01-01)

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

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

Pliability and approximating max-CSPs
af: Romero, M, et al.
Udgivet: (2023)

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

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