77 citations · 733 across the 54 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
cs.CC2012★ 51 cited
The complexity of finite-valued CSPs
Johan Thapper, Stanislav Zivny
We study the computational complexity of exact minimisation of rational-valued discrete functions. Let be a set of rational-valued functions on a fixed finite domain; such a se…
cs.CC2012★ 48 cited
An Algebraic Theory of Complexity for Discrete Optimisation
David A. Cohen, Martin C. Cooper, Paidi Creed +2
Discrete optimisation problems arise in many different areas and are studied under many different names. In many such problems the quantity to be optimised can be expressed as a su…
cs.CC2012★ 77 cited
The Power of Linear Programming for Valued CSPs
Johan Thapper, Stanislav Zivny
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…