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
Authors
Funding
London Mathematical Society
More from this funder
Bibliographic Details
- 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
Item Description
- Language:
- English
- UUID:
-
uuid:9ea2f7c0-298b-453c-a55c-54e8e7c5ec53
- Local pid:
- ora:11366
- Deposit date:
- 2015-05-06
Terms of use
- Copyright holder:
- Springer-Verlag Berlin Heidelberg
- Copyright date:
- 2015
If you are the owner of this record, you can report an update to it here: Report update to this record