The complexity of Boolean surjective general-valued CSPs

The complexity of Boolean surjective general-valued CSPs

他のバージョン（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...

書誌詳細
主要な著者:	Fulla, P, Zivny, S
フォーマット:	Journal article
出版事項:	2017

類似資料

The complexity of Boolean surjective general-valued CSPs
著者:: Fulla, P, 等
出版事項: (2017)

The complexity of Boolean surjective general-valued CSPs
著者:: Fulla, P, 等
出版事項: (2018)

On planar valued CSPs
著者:: Fulla, P, 等
出版事項: (2017)

On planar valued CSPs
著者:: Fulla, P, 等
出版事項: (2016)

Beyond boolean surjective VCSPs
著者:: Matl, G, 等
出版事項: (2019)

The complexity of finite-valued CSPs
著者:: Thapper, J, 等
出版事項: (2016)

The complexity of conservative valued CSPs
著者:: Kolmogorov, V, 等
出版事項: (2012)

The complexity of conservative valued CSPs
著者:: Kolmogorov, V, 等
出版事項: (2011)

The complexity of conservative valued CSPs
著者:: Kolmogorov, V, 等
出版事項: (2013)

The Complexity of Finite-Valued CSPs
著者:: Thapper, J, 等
出版事項: (2013)

The complexity of finite-valued CSPs
著者:: Thapper, J, 等
出版事項: (2013)

The complexity of conservative finite-valued CSPs
著者:: Kolmogorov, V, 等
出版事項: (2010)

PTAS for sparse general-valued CSPs
著者:: Mezei, BF, 等
出版事項: (2021)

PTAS for sparse general-valued CSPs
著者:: Mezei, B, 等
出版事項: (2023)

Using a min-cut generalisation to go beyond Boolean surjective VCSPs
著者:: Matl, G, 等
出版事項: (2020)

The complexity of general-valued CSPs seen from the other side
著者:: Carbonnel, C, 等
出版事項: (2018)

The limits of SDP relaxations for general-valued CSPs
著者:: Thapper, J, 等
出版事項: (2017)

The limits of SDP relaxations for general-valued CSPs
著者:: Thapper, J, 等
出版事項: (2018)

The power of Sherali-Adams relaxations for general-valued CSPs
著者:: Thapper, J, 等
出版事項: (2017)

The power of Sherali-Adams relaxations for general-valued CSPs
著者:: Thapper, J, 等
出版事項: (2015)

The complexity of counting surjective homomorphisms and compactions
著者:: Focke, J, 等
出版事項: (2017)

The complexity of counting surjective homomorphisms and compactions
著者:: Focke, J, 等
出版事項: (2019)

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
著者:: Backens, M, 等
出版事項: (2019)

The Power of Linear Programming for Valued CSPs
著者:: Thapper, J, 等
出版事項: (2012)

The power of linear programming for valued CSPs
著者:: Thapper, J, 等
出版事項: (2015)

The power of linear programming for valued CSPs
著者:: Thapper, J, 等
出版事項: (2012)

Sherali-Adams relaxations for valued CSPs
著者:: Thapper, J, 等
出版事項: (2015)

Necessary conditions for tractability of valued CSPs
著者:: Thapper, J, 等
出版事項: (2015)

The complexity of counting locally maximal satisfying assignments of Boolean CSPs
著者:: Goldberg, L, 等
出版事項: (2016)

Conditional Dichotomy of Boolean Ordered Promise CSPs
著者:: Joshua Brakensiek, 等
出版事項: (2023-01-01)

Sparsification of binary CSPs
著者:: Butti, S, 等
出版事項: (2020)

Sparsification of Binary CSPs
著者:: Butti, S, 等
出版事項: (2019)

Additive sparsification of CSPs
著者:: Pelleg, E, 等
出版事項: (2021)

Additive sparsification of CSPs
著者:: Pelleg, E, 等
出版事項: (2023)

Expected number of locally maximal solutions for random Boolean CSPs
著者:: Nadia Creignou, 等
出版事項: (2007-01-01)

Point-width and max-CSPs
著者:: Carbonnel, C, 等
出版事項: (2019)

Point-width and Max-CSPs
著者:: Carbonnel, C, 等
出版事項: (2020)

Pliability and approximating max-CSPs
著者:: Romero, M, 等
出版事項: (2023)

Treewidth-pliability and PTAS for Max-CSPs
著者:: Romero, M, 等
出版事項: (2021)

CLAP: A new algorithm for promise CSPs
著者:: Ciardo, L, 等
出版事項: (2023)