A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
Satoru Iwata, Lisa Fleischer, Satoru Fujishige · 2000
This paper presents the first combinatorial polynomialtime algorithm for minimizing submodular functions, answering an open question posed in 1981 by GrStschel, Love%sz, and Schrijver.The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter.The resulting algorithm runs in time bounded by a polynomial in the size of the underlying set and the largest length of the function value.The paper also presents a strongly polynomial-time version that runs in time bounded by a polynomial in the size of the underlying set independent of the function value.*A part of this work is done while on leave at the Fields Institute, Toronto, Canada.Partly supported