On Constant-factor Approximable Finite-valued CSPs
- 14:00 5th November 2014 ( week 4, Michaelmas Term 2014 )Lecture Theatre B, Wolfson Building, Parks Road
A recent result of Ene et al. says that, under a mild technical condition, the basic LP relaxation is optimal for constant-factor approximation for VCSPs unless the Unique Games Conjecture fails. We show that our characterisation problem for VCSPs reduces to the one for Min CSPs, and then use the algebraic approach to the CSP to characterise constraint languages such that the basic LP has a finite integrality gap for the corresponding Min CSP. We also show how this result can in principle be used to round solutions of the basic LP relaxation, and how, for several examples that cover all previously known cases, this leads to efficient constant-factor approximation algorithms. Finally, we improve the above mentioned UG-hardness of constant-factor approximation to NP-hardness for a class of Min CSPs.
This is joint work with Victor Dalmau (UPF Barcelona) and Rajsekar Manokaran (KTH Stockholm).