The power of Sherali-Adams relaxations for general-valued CSPs
Standa Živný ( University of Oxford )
- 14:00 15th June 2016 ( week 8, Trinity Term 2016 )Room 051, Wolfson Building, Parks Road
In this talk, I survey recent results on the power of LP relaxations (the basic LP relaxation and Sherali-Adams relaxations) in the context of valued constraint satisfaction problems (VCSP). We give precise characterisations of constraint languages for which these relaxations are exact, and also discuss computational complexity consequences. Based on several papers with Johan Thapper.
Share this:
