The limits of SDP relaxations for general-valued CSPs
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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Association for Computing Machinary
2018
|
| _version_ | 1797088765678714880 |
|---|---|
| author | Thapper, J Zivny, S |
| author_facet | Thapper, J Zivny, S |
| author_sort | Thapper, J |
| collection | OXFORD |
| description | 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 of the Sherali-Adams LP hierarchy, and (3) the support of Γ satisfies the “bounded width condition” (i.e., it contains weak near-unanimity operations of all arities). We show that if the support of Γ violates the bounded width condition then not only is VCSP(Γ) not solved by a constant level of the Sherali-Adams LP hierarchy, but it also requires linear levels of the Lasserre SDP hierarchy (also known as the sum-of-squares SDP hierarchy). For Γ 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 [STOC’15], our result implies that for any Γ whose support violates the bounded width condition no SDP relaxation of polynomial size solves VCSP(Γ). 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, ∞}-valued languages (CSPs), {0, 1}-valued languages (Min-CSPs/MaxCSPs), and Q-valued languages (finite-valued CSPs). |
| first_indexed | 2024-03-07T02:54:46Z |
| format | Journal article |
| id | oxford-uuid:aee4e87e-fcee-4fe9-9aba-3b9e67d0de81 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:54:46Z |
| publishDate | 2018 |
| publisher | Association for Computing Machinary |
| record_format | dspace |
| spelling | oxford-uuid:aee4e87e-fcee-4fe9-9aba-3b9e67d0de812022-03-27T03:45:49ZThe limits of SDP relaxations for general-valued CSPsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:aee4e87e-fcee-4fe9-9aba-3b9e67d0de81Symplectic Elements at OxfordAssociation for Computing Machinary2018Thapper, JZivny, SIt 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 of the Sherali-Adams LP hierarchy, and (3) the support of Γ satisfies the “bounded width condition” (i.e., it contains weak near-unanimity operations of all arities). We show that if the support of Γ violates the bounded width condition then not only is VCSP(Γ) not solved by a constant level of the Sherali-Adams LP hierarchy, but it also requires linear levels of the Lasserre SDP hierarchy (also known as the sum-of-squares SDP hierarchy). For Γ 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 [STOC’15], our result implies that for any Γ whose support violates the bounded width condition no SDP relaxation of polynomial size solves VCSP(Γ). 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, ∞}-valued languages (CSPs), {0, 1}-valued languages (Min-CSPs/MaxCSPs), and Q-valued languages (finite-valued CSPs). |
| 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 |