Journal article
The power of Sherali-Adams relaxations for general-valued CSPs
- Abstract:
-
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. Our characterisation has several algorithmic and complexity consequences. On the algorithmic side, we show that several no...
Expand abstract
Actions
Authors
Funding
Bibliographic Details
- Journal:
- ICALP 2015, Kyoto, Japan, July 6-10, 2015
- Publication date:
- 2015-01-01
- Source identifiers:
-
628595
Item Description
Terms of use
- Copyright holder:
- Thapper and Zivny
- Copyright date:
- 2015
- Notes:
- Full version of an ICALP'15 paper that is available here: https://ora.ox.ac.uk/objects/uuid:9ea2f7c0-298b-453c-a55c-54e8e7c5ec53
If you are the owner of this record, you can report an update to it here: Report update to this record