A Faster Scaling Algorithm for Minimizing Submodular Functions
Author:
- Satoru IwataSISatoru Iwata
- 1 January 2003
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 32 (4) , 833-840
Abstract
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 achieves strongly polynomial bound with the aid of distance labeling. Subsequently, Fleischer and Iwata have described a push/relabel version of Schrijver's algorithm to improve its time complexity. This paper combines the scaling scheme with the push/relabel framework to yield a faster combinatorial algorithm for submodular function minimization. The resulting algorithm improves over the previously best known bound by essentially a linear factor in the size of the underlying ground set.Keywords
This publication has 12 references indexed in Scilit:
- A faster capacity scaling algorithm for minimum cost submodular flowMathematical Programming, 2002
- A Fully Combinatorial Algorithm for Submodular Function MinimizationJournal of Combinatorial Theory, Series B, 2002
- A combinatorial strongly polynomial algorithm for minimizing submodular functionsJournal of the ACM, 2001
- A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial TimeJournal of Combinatorial Theory, Series B, 2000
- Geometric Algorithms and Combinatorial Optimization1988
- On submodular function minimizationCombinatorica, 1985
- Testing membership in matroid polyhedraJournal of Combinatorial Theory, Series B, 1984
- Submodular functions and convexity1983
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981
- Combinatorial Theory1979