A faster strongly polynomial time algorithm for submodular function minimization
成果类型：
Article
署名作者：
Orlin, James B.
署名单位：
Massachusetts Institute of Technology (MIT)
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-007-0189-2
发表日期：
2009
页码：
237-251
关键词：
摘要：
We consider the problem of minimizing a submodular function f defined on a set V with n elements. We give a combinatorial algorithm that runs in O(n(5)EO + n(6)) time, where EO is the time to evaluate f (S) for some S subset of V. This improves the previous best strongly polynomial running time by more than a factor of n. We also extend our result to ring families.