2 citations · 2 across the 2 of their papers we have counts for
2 papers
cs.CC2007
Hard constraint satisfaction problems have hard gaps at location 1
Peter Jonsson, Andrei Krokhin, Fredrik Kuivinen
An instance of Max CSP is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constra…
cs.CC2004★ 2 cited
The approximability of three-valued MAX CSP
Peter Jonsson, Mikael Klasson, Andrei Krokhin
In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to a…