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 ⁵EO  +  n ⁶) time, where EO is the time to evaluate f(S) for some . This improves the previous best strongly polynomial running time by more than a factor of n. We also extend our result to ring families.