The power of Sherali-Adams relaxations for general-valued CSPs
<p>We give a precise algebraic characterisation of the power of Sherali-Adams relaxations for solvability of valued constraint satisfaction problems to optimality. The condition is that of bounded width which has already been shown to capture the power of local consistency methods for decision...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Society for Industrial and Applied Mathematics
2017
|
| _version_ | 1797081053948542976 |
|---|---|
| author | Thapper, J Zivny, S |
| author_facet | Thapper, J Zivny, S |
| author_sort | Thapper, J |
| collection | OXFORD |
| description | <p>We give a precise algebraic characterisation of the power of Sherali-Adams relaxations for solvability of valued constraint satisfaction problems to optimality. The condition is that of bounded width which has already been shown to capture the power of local consistency methods for decision CSPs and the power of semidefinite programming for robust approximation of CSPs.</p> <br/> <p>Our characterisation has several algorithmic and complexity consequences. On the algorithmic side, we show that several novel and many known valued constraint languages are tractable via the third level of the Sherali-Adams relaxation. For the known languages, this is a significantly simpler algorithm than the previously obtained ones. On the complexity side, we obtain a dichotomy theorem for valued constraint languages that can express an injective unary function. This implies a simple proof of the dichotomy theorem for conservative valued constraint languages established by Kolmogorov and Živný [JACM’13], and also a dichotomy theorem for the exact solvability of Minimum-Solution problems. These are generalisations of Minimum-Ones problems to arbitrary finite domains. Our result improves on several previous classifications by Khanna et al. [SICOMP’00], Jonsson et al. [SICOMP’08], and Uppman [ICALP’13].</p> |
| first_indexed | 2024-03-07T01:09:06Z |
| format | Journal article |
| id | oxford-uuid:8c5fd2f8-0e4f-4c10-a4e0-984634fdb67b |
| institution | University of Oxford |
| last_indexed | 2024-03-07T01:09:06Z |
| publishDate | 2017 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:8c5fd2f8-0e4f-4c10-a4e0-984634fdb67b2022-03-26T22:44:08ZThe power of Sherali-Adams relaxations for general-valued CSPsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:8c5fd2f8-0e4f-4c10-a4e0-984634fdb67bSymplectic Elements at OxfordSociety for Industrial and Applied Mathematics2017Thapper, JZivny, S<p>We give a precise algebraic characterisation of the power of Sherali-Adams relaxations for solvability of valued constraint satisfaction problems to optimality. The condition is that of bounded width which has already been shown to capture the power of local consistency methods for decision CSPs and the power of semidefinite programming for robust approximation of CSPs.</p> <br/> <p>Our characterisation has several algorithmic and complexity consequences. On the algorithmic side, we show that several novel and many known valued constraint languages are tractable via the third level of the Sherali-Adams relaxation. For the known languages, this is a significantly simpler algorithm than the previously obtained ones. On the complexity side, we obtain a dichotomy theorem for valued constraint languages that can express an injective unary function. This implies a simple proof of the dichotomy theorem for conservative valued constraint languages established by Kolmogorov and Živný [JACM’13], and also a dichotomy theorem for the exact solvability of Minimum-Solution problems. These are generalisations of Minimum-Ones problems to arbitrary finite domains. Our result improves on several previous classifications by Khanna et al. [SICOMP’00], Jonsson et al. [SICOMP’08], and Uppman [ICALP’13].</p> |
| spellingShingle | Thapper, J Zivny, S The power of Sherali-Adams relaxations for general-valued CSPs |
| title | The power of Sherali-Adams relaxations for general-valued CSPs |
| title_full | The power of Sherali-Adams relaxations for general-valued CSPs |
| title_fullStr | The power of Sherali-Adams relaxations for general-valued CSPs |
| title_full_unstemmed | The power of Sherali-Adams relaxations for general-valued CSPs |
| title_short | The power of Sherali-Adams relaxations for general-valued CSPs |
| title_sort | power of sherali adams relaxations for general valued csps |
| work_keys_str_mv | AT thapperj thepowerofsheraliadamsrelaxationsforgeneralvaluedcsps AT zivnys thepowerofsheraliadamsrelaxationsforgeneralvaluedcsps AT thapperj powerofsheraliadamsrelaxationsforgeneralvaluedcsps AT zivnys powerofsheraliadamsrelaxationsforgeneralvaluedcsps |