101 citations · 355 across the 29 of their papers we have counts for
11 papers · 1 filter
Generalized minimum 0-extension problem and discrete convexity
Martin Dvorak, Vladimir Kolmogorov
Given a fixed finite metric space , the {\em minimum -extension problem}, denoted as ${\tt 0\mbox{-}Ext}[μ]$, is equivalent to the following optimization problem: minimiz…
Testing the complexity of a valued CSP language
Vladimir Kolmogorov
A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite se…
Even Delta-Matroids and the Complexity of Planar Boolean CSPs
Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek
The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each vari…
Effectiveness of Structural Restrictions for Hybrid CSPs
Vladimir Kolmogorov, Michal Rolinek, Rustem Takhanov
Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism…
The Complexity of General-Valued CSPs
Vladimir Kolmogorov, Andrei Krokhin, Michal Rolinek
An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending o…
The power of linear programming for general-valued CSPs
Vladimir Kolmogorov, Johan Thapper, Stanislav Zivny
Let , called the domain, be a fixed finite set and let , called the valued constraint language, be a fixed set of functions of the form , wh…
The power of linear programming for valued CSPs: a constructive characterization
Vladimir Kolmogorov
A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the pr…
The complexity of conservative 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…
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…