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 t...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Publisher copy:
10.1137/16M1079245

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Name:
Horizon 2020
Grant:
714532
More from this funder
Name:
Royal Society
Funding agency for:
Zivny, S
Publisher:
Society for Industrial and Applied Mathematics
Journal:
SIAM Journal on Computing More from this journal
Volume:
46
Issue:
4
Pages:
1241–1279
Publication date:
2017-07-01
Acceptance date:
2017-03-02
DOI:
ISSN:
1095-7111
Pubs id:
pubs:683789
UUID:
uuid:8c5fd2f8-0e4f-4c10-a4e0-984634fdb67b
Local pid:
pubs:683789
Source identifiers:
683789
Deposit date:
2017-03-02

Terms of use


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