The limits of SDP relaxations for general-valued CSPs

The limits of SDP relaxations for general-valued CSPs

他のバージョン（1件）を表示する

It has been shown that for a general-valued constraint language Γ the following statements are equivalent: (1) any instance of VCSP(Γ) can be solved to optimality using a constant level of the Sherali-Adams LP hierarchy, (2) any instance of VCSP(Γ) can be solved to optimality using the third level o...

書誌詳細
主要な著者:	Thapper, J, Zivny, S
フォーマット:	Journal article
出版事項:	Association for Computing Machinary 2018

類似資料

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

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

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

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

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

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

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

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)

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

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

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

The complexity of Boolean surjective general-valued CSPs
著者:: Fulla, P, 等
出版事項: (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, 等
出版事項: (2016)

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

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 general-valued CSPs seen from the other side
著者:: Carbonnel, C, 等
出版事項: (2018)

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

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)

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)

On singleton arc consistency for CSPs defined by monotone patterns
著者:: Carbonnel, C, 等
出版事項: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
著者:: Carbonnel, C, 等
出版事項: (2018)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
著者:: Cooper, M, 等
出版事項: (2017)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
著者:: Cooper, M, 等
出版事項: (2016)

Small Promise CSPs that reduce to large CSPs
著者:: Alexandr Kazda, 等
出版事項: (2022-08-01)

Tractable classes of binary CSPs defined by excluded topological minors
著者:: Cohen, D, 等
出版事項: (2015)

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
著者:: Martin C. Cooper, 等
出版事項: (2017-12-01)

Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation
著者:: A. Suebsriwichai, 等
出版事項: (2017-01-01)