8 citations · 10 across the 5 of their papers we have counts for
5 papers
Min CSP on Four Elements: Moving Beyond Submodularity
Peter Jonsson, Fredrik Kuivinen, Johan Thapper
We report new results on the complexity of the valued constraint satisfaction problem (VCSP). Under the unique games conjecture, the approximability of finite-valued VCSP is fairly…
On the Complexity of Submodular Function Minimisation on Diamonds
Fredrik Kuivinen
Let be a finite lattice and let be a positive integer. A function is said to be submodular if $f(\tup{a} \sqcap \tup{b}) + f(\tup…
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…
Approximability of Bounded Occurrence Max Ones
Fredrik Kuivinen
We study the approximability of Max Ones when the number of variable occurrences is bounded by a constant. For conservative constraint languages (i.e., when the unary relations are…
Approximability of Integer Programming with Generalised Constraints
Peter Jonsson, Fredrik Kuivinen, Gustav Nordh
We study a family of problems, called \prob{Maximum Solution}, where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables…