Towards a Characterization of Constant-Factor Approximable Finite-Valued CSPs

Victor Dalmau, Andrei Krokhin, Rajsekar Manokaran

In this paper we study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language Γ consisting of finitary functions on…