Conference item icon

Conference item

Sherali-Adams relaxations for valued CSPs

Abstract:

We consider Sherali-Adams linear programming relaxations for solving valued constraint satisfaction problems to optimality. The utility of linear programming relaxations in this context have previously been demonstrated using the lowest possible level of this hierarchy under the name of the basic linear programming relaxation (BLP). It has been shown that valued constraint languages containing only finite-valued weighted relations are tractable if, and only if, the integrality gap of the BLP ...

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

Actions


Access Document


Authors


More by this author
Institution:
University of Oxford
Department:
Mathematical,Physical & Life Sciences Division - Computer Science,Department of
Role:
Author
More from this funder
Funding agency for:
Stanislav Živný
London Mathematical Society More from this funder
Publisher:
Springer Berlin Heidelberg Publisher's website
Volume:
Series Volume: 9134
Pages:
1058-1069
DOI:
ISSN:
0302-9743
URN:
uuid:9ea2f7c0-298b-453c-a55c-54e8e7c5ec53
Local pid:
ora:11366
ISBN:
978-3-662-47672-7
Language:
English

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