101 citations · 355 across the 29 of their papers we have counts for
4 papers · 1 filter
A dichotomy theorem for conservative general-valued CSPs
Vladimir Kolmogorov
We study the complexity of valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a \emph{constraint language}, a fixed set of cost functions over…
Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms
Vladimir Kolmogorov, Stanislav Zivny
We study optimisation problems that can be formulated as valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a \emph{constraint language}, a fix…
The complexity of conservative finite-valued CSPs
Vladimir Kolmogorov, Stanislav Zivny
We study the complexity of valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a \emph{constraint language}, a fixed set of cost functions over…
Minimizing a sum of submodular functions
Vladimir Kolmogorov
We consider the problem of minimizing a function represented as a sum of submodular terms. We assume each term allows an efficient computation of {\em exchange capacities}. This ho…