Improved algorithms for submodular function minimization and submodular flow
Lisa Fleischer, Satoru Iwata · 2000
Very recently, two groups of researchers independently developed the first combinatorial, strongly polynomial-time algorithms for submodular function minimization (Iwata, Fleischer, Fujishige; and Schrijver).In this paper, we improve on these algorithms and show that the ideas generated in the design of these algorithms are helpful in other contexts.This work demonstrates one use of combinatorial algorithms for submodular function minimization.In particular we accomplish three things.First, we improve the complexity of Schrijver's algorithm by designing a push-relabel algorithm for submodular function minimization (SFM).Second, we exploit the common structure shared between submodular function minimization and maximum submodular flow to design the first algorithm for maximum submodular flow that does not depend on an oracle for SFM.The overall time complexity is the same as for SFM.Finally, we design the first algorithms for minimum cost submodular flow that do not depend on an oracle for SFM, using the framework of submodular function minimization of Iwata, Fleischer, Fujishige.We show that optimal dual solutions can be computed in the same time as SFM, and that optimal primal solutions can thus be obtained with one additional maximum submodular flow computation.We give both weakly and strongly polynomial versions.* Part of this work done while on leave at the Fields Institute, Toronto, Canada.