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: | , |
|---|---|
| Format: | Conference item |
| Published: |
ACM/IEEE
2017
|
| _version_ | 1797091287845830656 |
|---|---|
| author | Thapper, J Zivny, S |
| author_facet | Thapper, J Zivny, S |
| author_sort | Thapper, J |
| collection | OXFORD |
| description | <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}(\Gamma)$ can be solved to optimality using the third level of the Sherali-Adams LP hierarchy; (3) the support of $\Gamma$ satisfies the "bounded width condition", i.e., it contains weak near-unanimity operations of all arities. </p> <p>We show that if the support of $\Gamma$ violates the bounded with condition then not only is $\operatorname{VCSP}(\Gamma)$ not solved by a constant level of the Sherali-Adams LP hierarchy but it is also not solved by $\Omega(n)$ levels of the Lasserre SDP hierarchy (also known as the sum-of-squares SDP hierarchy). For $\Gamma$ corresponding to linear equations in an Abelian group, this result follows from existing work on inapproximability of Max-CSPs. By a breakthrough result of Lee, Raghavendra, and Steurer, our result implies that for any $\Gamma$ whose support violates the bounded width condition no SDP relaxation of polynomial-size solves $\operatorname{VCSP}(\Gamma)$. </p> <p>We establish our result by proving that various reductions preserve exact solvability by the Lasserre SDP hierarchy (up to a constant factor in the level of the hierarchy). Our results hold for general-valued constraint languages, i.e., sets of functions on a fixed finite domain that take on rational or infinite values, and thus also hold in notable special cases of $\{0,\infty\}$-valued languages (CSPs), $\{0,1\}$-valued languages (Min-CSPs/Max-CSPs), and $\mathbb{Q}$-valued languages (finite-valued CSPs).</p> |
| first_indexed | 2024-03-07T03:30:49Z |
| format | Conference item |
| id | oxford-uuid:baa6f679-80b6-4578-a777-fe7a244347a4 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:30:49Z |
| publishDate | 2017 |
| publisher | ACM/IEEE |
| record_format | dspace |
| spelling | oxford-uuid:baa6f679-80b6-4578-a777-fe7a244347a42022-03-27T05:11:20ZThe limits of SDP relaxations for general-valued CSPsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:baa6f679-80b6-4578-a777-fe7a244347a4Symplectic Elements at OxfordACM/IEEE2017Thapper, JZivny, S<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}(\Gamma)$ can be solved to optimality using the third level of the Sherali-Adams LP hierarchy; (3) the support of $\Gamma$ satisfies the "bounded width condition", i.e., it contains weak near-unanimity operations of all arities. </p> <p>We show that if the support of $\Gamma$ violates the bounded with condition then not only is $\operatorname{VCSP}(\Gamma)$ not solved by a constant level of the Sherali-Adams LP hierarchy but it is also not solved by $\Omega(n)$ levels of the Lasserre SDP hierarchy (also known as the sum-of-squares SDP hierarchy). For $\Gamma$ corresponding to linear equations in an Abelian group, this result follows from existing work on inapproximability of Max-CSPs. By a breakthrough result of Lee, Raghavendra, and Steurer, our result implies that for any $\Gamma$ whose support violates the bounded width condition no SDP relaxation of polynomial-size solves $\operatorname{VCSP}(\Gamma)$. </p> <p>We establish our result by proving that various reductions preserve exact solvability by the Lasserre SDP hierarchy (up to a constant factor in the level of the hierarchy). Our results hold for general-valued constraint languages, i.e., sets of functions on a fixed finite domain that take on rational or infinite values, and thus also hold in notable special cases of $\{0,\infty\}$-valued languages (CSPs), $\{0,1\}$-valued languages (Min-CSPs/Max-CSPs), and $\mathbb{Q}$-valued languages (finite-valued CSPs).</p> |
| spellingShingle | Thapper, J Zivny, S The limits of SDP relaxations for general-valued CSPs |
| title | The limits of SDP relaxations for general-valued CSPs |
| title_full | The limits of SDP relaxations for general-valued CSPs |
| title_fullStr | The limits of SDP relaxations for general-valued CSPs |
| title_full_unstemmed | The limits of SDP relaxations for general-valued CSPs |
| title_short | The limits of SDP relaxations for general-valued CSPs |
| title_sort | limits of sdp relaxations for general valued csps |
| work_keys_str_mv | AT thapperj thelimitsofsdprelaxationsforgeneralvaluedcsps AT zivnys thelimitsofsdprelaxationsforgeneralvaluedcsps AT thapperj limitsofsdprelaxationsforgeneralvaluedcsps AT zivnys limitsofsdprelaxationsforgeneralvaluedcsps |