Skip to main content

On Constant-factor Approximable Finite-valued CSPs

Andrei Krokhin ( Durham University )
We study the approximability of minimisation problems related to CSP, namely the (finite-)valued constraint satisfaction problems (VCSPs) and their special case, the minimum constraint satisfaction problems (Min CSPs), all with a fixed finite constraint language Gamma. In this talk, we will focus on characterising such problems that admit a constant-factor approximation algorithm.

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).

Speaker bio

Andrei Krokhin obtained PhD in Mathematics from Ural State University, Yekaterinburg, Russia, where he then worked as a lecturer for several years. In 2000, he moved to the UK and held positions at the Universities of Oxford and Warwick before moving to Durham University in 2004, where he is currently Professor in Computer Science.

 

 

Share this: