The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
复制标题
有限值 CSP 线性规划的威力：建设性表征
DOI：
10.1007/978-3-642-39206-1_53
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
V. Kolmogorov
中科院分区：
文献类型：
--
作者：
V. Kolmogorov
一类有值约束满足问题（vcsp）的特征是有值约束语言，即有限域上的一组固定的代价函数。问题的一个实例是由语言的代价函数的总和来指定的，目标是最小化总和。
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 problem is specified by a sum of cost functions from the language with the goal to minimise the sum.
We study which classes of finite-valued languages can be solved exactly by the basic linear programming relaxation (BLP). Thapper and Živný showed [20] that if BLP solves the language then the language admits a binary commutative fractional polymorphism. We prove that the converse is also true. This leads to a necessary and a sufficient condition which can be checked in polynomial time for a given language. In contrast, the previous necessary and sufficient condition due to [20] involved infinitely many inequalities.
More recently, Thapper and Živný [21] showed (using, in particular, a technique introduced in this paper) that core languages that do not satisfy our condition are NP-hard. Taken together, these results imply that a finite-valued language can either be solved using Linear Programming or is NP-hard.
偏斜双子模性和有价值的 CSP
影响因子：
1.6
作者：
Huber A
通讯作者：
Huber A