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)

On planar valued CSPs
द्वारा: Fulla, P, और अन्य
प्रकाशित: (2016)

On planar valued CSPs
द्वारा: Fulla, P, और अन्य
प्रकाशित: (2017)

The complexity of Boolean surjective general-valued CSPs
द्वारा: Fulla, P, और अन्य
प्रकाशित: (2018)

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)

Exploiting Sparsity in SDP Relaxation for Harmonic Balance Method
द्वारा: Cheng-Hsiung Yang, और अन्य
प्रकाशित: (2020-01-01)

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)

The SDP's Electoral Limits: The 2014 Presidential Elections
द्वारा: Daniel Buti
प्रकाशित: (2015-03-01)

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)