A combinatorial strongly polynomial algorithm for minimizing submodular functions.

This paper presents a combinatorial polynomial-time algorithm for minimizing submodular functions, answering an open question posed in 1981 by Grötschel, Lová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...

Full description

Bibliographic Details

Published in:	Journal of the ACM 48, 4 (2001).
Main Author:	Iwata, Satoru
Format:	Article
Language:	English
Subjects:	Theory of computation. Analysis of algorithms and problem complexity. Nonnumerical algorithms and problems. Computations on discrete structures. Mathematics of computing. Discrete mathematics. Combinatorics. Combinatorial algorithms. Algorithms.