78 citations · 116 across the 14 of their papers we have counts for
3 papers · 1 filter
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…
Binarisation for Valued Constraint Satisfaction Problems
David A. Cohen, Martin C. Cooper, Peter G. Jeavons +3
We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the alge…
Robust algorithms with polynomial loss for near-unanimity CSPs
Víctor Dalmau, Marcin Kozik, Andrei Krokhin +3
An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain…