A strongly polynomial-time algorithm for minimizing submodular functions
Satoru Iwata, Lisa Fleischer, Satoru Fujishige · 1999
This paper presents a combinatorial polynomial-time algorithm for minimizing submodular set functions. 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. These are the first combinatorial algorithms for submodular function minimization that run in (strongly) polynomial time. Key words: submodular function, combinatorial optimization, strongly polynomial-time algorithm 1 Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka 5608531, Japan. E-mail: [email protected]. Partly supported by Grants-in-Aid for Scientific Research from Ministry of Education, Science, Sports, and Culture of Japan. 2 Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027, USA. E-mail: [email protected]. This work done while on leave at Center for Operations Research and Econometrics, Universit'e catholique de Louvain, Belgium. 3 Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka 560-8531, Japan. E-mail: [email protected]. Partly supported by Grants-in-Aid for Scientific Research from Ministry of Education, Science, Sports, and Culture of Japan. This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office,...