The Power of Linear Programming for Valued CSPs
The Power of Linear Programming for Valued CSPs
复制标题
线性规划对有价值的 CSP 的威力
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Stanislav Živný
中科院分区：
文献类型：
--
作者：
Johan Thapper;Stanislav Živný
一类有价值的约束满足问题（VCSP）的特征是有价值的约束语言，即有限域上的一组固定成本函数。问题的实例由语言中的成本函数之和指定，目标是最小化总和。该框架包括并概括了经过充分研究的约束满足问题（CSP）和最大约束满足问题（Max-CSP）。我们的主要结果是有价值约束语言的精确代数表征，其实例可以通过基本线性规划松弛来精确求解。利用这个结果，我们获得了几个新颖且先前广泛开放的 VCSP 类的易处理性，包括关于有价值约束语言的问题：（1）任意格上的子模，（2）任意有限域上的双子模（也称为 k-sub 模），（3）任意树上的弱（因此强）树子模。
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. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs). Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation. Using this result, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) sub modular on arbitrary lattices, (2) bisubmodular (also known as k-sub modular) on arbitrary finite domains, (3) weakly (and hence strongly) tree-sub modular on arbitrary trees.
影响因子：
1.6
作者：
Cohen D
通讯作者：
Cohen D