A Submodular Function Minimization Algorithm Based on the Minimum-Norm Base ⁄

A Submodular Function Minimization Algorithm Based on the Minimum-Norm Base ⁄
复制标题

DOI：
--
复制
发表时间：
2009
期刊：
--
影响因子：
--
通讯作者：
S. Fujishige;S. Isotani
S. Fujishige;S. Isotani
中科院分区：
其他
文献类型：
--
作者：
S. Fujishige;S. Isotani

文献摘要

被引文献

相似文献

我们考虑最小范数点算法在次模函数极小化中的应用。虽然最近已经获得了次模函数极小化（SFM）的组合多项式算法，但是仍然存在降低SFM算法复杂度和构造实用快速SFM算法的问题。我们通过最小范数点算法给出了一些可能的解决方法。次模函数极小化的计算结果表明，我们的算法优于现有的多项式算法的SFM。
We consider an application of the minimum-norm-point algorithm to submodular function minimization. Although combinatorial polynomial algorithms for submodular function minimization (SFM) have recently been obtained, there still remain (open) problems of reducing the complexity of the SFM algorithms and of constructing a practically fast SFM algorithms. We show some possible approach to the problems by means of the minimum-norm-point algorithm. Computational results on submodular function minimization reveal that our algorithm outperforms existing polynomial algorithms for SFM.