Submodular Function Maximization on the Bounded Integer Lattice
Submodular Function Maximization on the Bounded Integer Lattice
复制标题
有界整数格上的子模函数最大化
DOI：
10.1007/978-3-319-28684-6_12
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Britta Peis
中科院分区：
文献类型：
--
作者：
Corinna Gottschalk;Britta Peis
我们考虑了有界整数格上的子模函数的极大化问题。作为子模集合函数的直接推广，是子模的，其中IFFOR ALL表示元素最小值和最大值。目标是找到一个向量x最大化f(X)。在这篇文章中，我们使用一个受[2]启发的框架给出了一个确定性近似。我们还提供了一个例子，表明分析是严密的，并产生了对修改算法的可能性的额外洞察。此外，我们还考察了子模集合函数最大化的一些结构差异，这些差异使我们的问题更难解决。
We consider the problem of maximizing a submodular function on the bounded integer lattice. As a direct generalization of submodular set functions,is submodular, iffor allwhereanddenote element-wise minimum and maximum. The objective is finding a vectorxmaximizingf(x). In this paper, we present a deterministic-approximation using a framework inspired by [2]. We also provide an example that shows the analysis is tight and yields additional insight into the possibilities of modifying the algorithm. Moreover, we examine some structural differences to maximization of submodular set functions which make our problem harder to solve.
登录
查看更多内容
DOI：
10.1007/978-3-540-79309-0_21
发表时间：
2008-04
期刊：
--
影响因子：
--
作者：
U. Faigle;Britta Peis
通讯作者：
U. Faigle;Britta Peis
DOI：
10.1016/0095-8956(90)90070-g
发表时间：
1990-12
期刊：
J. Comb. Theory B
影响因子：
--
作者：
É. Tardos
通讯作者：
É. Tardos
DOI：
10.1016/s0166-218x(02)00458-4
发表时间：
2003-09
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
L. Fleischer;S. Iwata
通讯作者：
L. Fleischer;S. Iwata
某些类别的组合线性规划的两阶段贪婪算法
DOI：
--
发表时间：
2008
期刊：
TALG
影响因子：
--
作者：
U. Faigle;Britta Peis
通讯作者：
Britta Peis
DOI：
--
发表时间：
1984
期刊：
影响因子：
--
作者：
U. Faigle
通讯作者：
U. Faigle