A faster strongly polynomial time algorithm for submodular function minimization

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.