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

Actions


Access Document


Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
London Mathematical Society More from this funder
More from this funder
Funding agency for:
Živný, S
Publisher:
Springer Berlin Heidelberg Publisher's website
Volume:
Series Volume: 9134
Pages:
1058-1069
Host title:
Automata, Languages, and Programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I
DOI:
ISSN:
0302-9743
ISBN:
9783662476727
Language:
English
UUID:
uuid:9ea2f7c0-298b-453c-a55c-54e8e7c5ec53
Local pid:
ora:11366
Deposit date:
2015-05-06

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