期刊
MATHEMATICAL PROGRAMMING
卷 118, 期 2, 页码 237-251出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-007-0189-2
关键词
-
类别
资金
- Office of Naval Research [N0001498-1-0317]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据