The limits of SDP relaxations for general-valued CSPs
<p>It has been shown that for a general-valued constraint language $\Gamma$ the following statements are equivalent: (1) any instance of $\operatorname{VCSP}(\Gamma)$ can be solved to optimality using a constant level of the Sherali-Adams LP hierarchy; (2) any instance of $\operatorname{VCSP}(...
Main Authors: | Thapper, J, Zivny, S |
---|---|
Format: | Conference item |
Published: |
ACM/IEEE
2017
|
Similar Items
-
The limits of SDP relaxations for general-valued CSPs
by: Thapper, J, et al.
Published: (2018) -
The power of Sherali-Adams relaxations for general-valued CSPs
by: Thapper, J, et al.
Published: (2017) -
The power of Sherali-Adams relaxations for general-valued CSPs
by: Thapper, J, et al.
Published: (2015) -
Sherali-Adams relaxations for valued CSPs
by: Thapper, J, et al.
Published: (2015) -
The complexity of finite-valued CSPs
by: Thapper, J, et al.
Published: (2013)