Skew Bisubmodularity and Valued CSPs
Skew Bisubmodularity and Valued CSPs
复制标题
偏斜双子模性和有价值的 CSP
DOI：
10.1137/120893549
复制
发表时间：
2014
影响因子：
1.6
通讯作者：
Huber A
中科院分区：
文献类型：
--
作者：
Huber A
（有限）值约束满足问题（VCSP）的一个实例由有限变量集、有限值域和（有理值）函数和给出，每个函数依赖于变量的一个子集。目标是找到一个赋值给变量，使总和最小。我们研究（假设）这个非常普遍的问题的复杂性如何取决于实例中允许的函数。Cohen等人对变量只能取两个值的情况进行了分类：本质上，子模函数产生了唯一可处理的情况，任何非子模函数都可以在某种特定意义上用来表示NP-hardMax Cutproblem。我们研究变量可以取三个值的情况。我们确定了一个新的无限族条件，其中包括双亚模性作为一种特殊情况，可以统称为偏双模性。Thapper和Živný最近的结果表明，该条件可以用线性规划求解相应的VCSP。我们证明了关于全阶的子模性和偏双模性产生了唯一可处理的情况，并且在所有其他情况下，仍然可以表示Max cut_max。我们还表明，我们对可处理病例的描述是严格的；也就是说，没有一个条件可以省略。
An instance of the (finite-)valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of values, and a sum of (rational-valued) functions, with each function depending on a subset of the variables. The goal is to find an assignment of values to the variables that minimizes the sum. We study (assuming that) how the complexity of this very general problem depends on the functions allowed in the instances. The case when the variables can take only two values was classified by Cohen et al.: essentially, submodular functions give rise to the only tractable case, and any non--submodular function can be used to express, in a certain specific sense, the NP-hardMax Cutproblem. We investigate the case when the variables can take three values. We identify a new infinite family of conditions that includes bisubmodularity as a special case and which can collectively be called skew bisubmodularity. By a recent result of Thapper and Živný, this condition implies that the corresponding VCSP can be solved by linear programming. We prove that submodularity, with respect to a total order, and skew bisubmodularity give rise to the only tractable cases, and, in all other cases, again,Max Cutcan be expressed. We also show that our characterization of tractable cases is tight; that is, none of the conditions can be omitted.
登录
查看更多内容
推广子模性和喇叭子句：由锦标赛对多态性定义的可处理优化问题
影响因子：
1.1
作者：
D. Cohen;Martin C. Cooper;P. Jeavons
通讯作者：
P. Jeavons
论独特游戏猜想（特邀调查）
DOI：
--
发表时间：
2005
期刊：
2010 IEEE 25th Annual Conference on Computational Complexity
影响因子：
--
作者：
Subhash Khot
通讯作者：
Subhash Khot
影响因子：
1.6
作者：
Cohen D
通讯作者：
Cohen D
有限值 CSP 线性规划的威力：建设性表征
DOI：
10.1007/978-3-642-39206-1_53
发表时间：
2013
期刊：
2013 IEEE 25th International Conference on Tools with Artificial Intelligence
影响因子：
--
作者：
V. Kolmogorov
通讯作者：
V. Kolmogorov
影响因子：
32.8
作者：
Wainwright, Martin J.;Jordan, Michael I.
通讯作者：
Jordan, Michael I.