A push-relabel framework for submodular function minimization and applications to parametric optimization
A push-relabel framework for submodular function minimization and applications to parametric optimization
复制标题
DOI：
10.1016/s0166-218x(02)00458-4
复制
发表时间：
2003-09
期刊：
影响因子：
--
通讯作者：
L. Fleischer;S. Iwata
中科院分区：
文献类型：
--
作者：
L. Fleischer;S. Iwata
最近，Iwata, Fleischer， Fujishige和Schrijver独立地设计了第一个用于次模函数最小化的组合强多项式算法。在本文中，我们通过设计一个用于子模函数最小化（SFM）的push-relabel框架来改善Schrijver算法的运行时间。我们还扩展了该算法，在与单个SFM相同的渐近运行时间内，对子模函数的强映射序列进行了参数最小化。应用程序包括用于查找字典最优基的有效算法。
Recently, the first combinatorial strongly polynomial algorithms for submodular function minimization have been devised independently by Iwata, Fleischer, and Fujishige and by Schrijver. In this paper, we improve the running time of Schrijver's algorithm by designing a push-relabel framework for submodular function minimization (SFM). We also extend this algorithm to carry out parametric minimization for a strong map sequence of submodular functions in the same asymptotic running time as a single SFM. Applications include an efficient algorithm for finding a lexicographically optimal base.