Combinatorial strongly polynomial algorithms for minimizing submodular functions have been developed by Iwata, Fleischer, and Fujishige (IFF) and by Schrijver. The IFF algorithm employs a scaling scheme for submodular functions, whereas Schrijver's algorithm exploits distance labeling. This paper combines these two techniques to yield a faster combinatorial algorithm for submodular function minimization. The resulting algorithm improves over the previously best known bound by an almost linear factor in the size of the underlying ground set.
展开▼
