We present the first combinatorial, polynomial time algorithms for submodular function minimization, answering an open question posed by Grotschel, Lovasz, and Schrijver in 1981. The algorithms use a variant of a min-max relation due to Edmonds, and build on ideas in the pseudopolynomial time, augmenting path algorithm of Cunningham. A new technique of the algorithms is to relax the submodular function by a scaling parameter times the boundary of a flow in a complete directed graph; and to use augmenting paths in this directed graph. This is joint work with Satoru Iwata and Satoru Fujishige, both of Osaka University.

The techniques inspiring this algorithm were developed in a series of recent papers on algorithms for submodular flow. In turn, we can now use this algorithm to design more efficient algorithms for submodular flow. Time permitting, we will discuss the relations between these earlier algorithms and this more recent improvement.