Oracle Tractability of Skew Bisubmodular Functions
Oracle Tractability of Skew Bisubmodular Functions
复制标题
Oracle 偏斜双子模函数的可处理性
DOI：
10.1137/130936038
复制
发表时间：
2014
影响因子：
0.8
通讯作者：
Huber A
中科院分区：
文献类型：
--
作者：
Huber A
在本文中，我们考虑作者和鲍威尔最近提出的偏双子模函数。我们构造了一个斜双子模函数的凸扩展，我们将其称为 Lovász 扩展，以对应于子模情况。我们使用这个扩展来证明由预言机给出的偏双子模函数可以在多项式时间内最小化。
In this paper we consider skew bisubmodular functions as recently introduced by the authors and Powell. We construct a convex extension of a skew bisubmodular function which we call Lovász extension in correspondence to the submodular case. We use this extension to show that skew bisubmodular functions given by an oracle can be minimized in polynomial time.
登录
查看更多内容
最大化乘积格上的超模函数，并应用于最大约束满足
DOI：
10.1137/060669565
发表时间：
2008
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
A. Krokhin;B. Larose
通讯作者：
B. Larose
线性规划对有价值的 CSP 的威力
DOI：
--
发表时间：
2012
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Johan Thapper;Stanislav Živný
通讯作者：
Stanislav Živný
偏斜双子模性和有价值的 CSP
影响因子：
1.6
作者：
Huber A
通讯作者：
Huber A
定向子模性、二重体和定向子模流
影响因子：
2.7
作者：
L. Qi
通讯作者：
L. Qi
Delta-拟阵、跳跃系统和双亚模多面体
影响因子：
0.8
作者：
A. Bouchet;W. Cunningham
通讯作者：
W. Cunningham