Journal article icon

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


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
More from this funder
Funding agency for:
Zivny, S
Journal:
ICALP 2015, Kyoto, Japan, July 6-10, 2015
Publication date:
2015-01-01
URN:
uuid:1e49f3ba-9c7b-47aa-9900-261d3e4d1076
Source identifiers:
628595
Local pid:
pubs:628595
Keywords:

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP