Journal article icon

Journal article

The limits of SDP relaxations for general-valued CSPs

Abstract:

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

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1145/3201777

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More from this funder
Funding agency for:
Zivny, S
Publisher:
Association for Computing Machinary Publisher's website
Journal:
ACM Transactions on Computation Theory Journal website
Volume:
10
Issue:
3
Pages:
Article: 12
Publication date:
2018-06-08
Acceptance date:
2018-03-13
DOI:
ISSN:
1942-3454
Pubs id:
pubs:829420
URN:
uri:aee4e87e-fcee-4fe9-9aba-3b9e67d0de81
UUID:
uuid:aee4e87e-fcee-4fe9-9aba-3b9e67d0de81
Local pid:
pubs:829420

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