A fully combinatorial algorithm for submodular function minimization. (Q1850585)

Let \(U\) be a finite nonempty set of cardinality \(n\). A function \(f\) defined on the subsets of \(U\) is submodular if it satisfies \(f(X)+f(Y)\geq f(X\cap Y)+f(X\cup Y)\) for all \(X,Y\subseteq U\). The author, \textit{L. Fleischer} and \textit{S. Fujishige} [J. ACM 48, No. 4, 761--777 (2001; Zbl 1127.90402)] and \textit{A. Schrijver} [J. Combin. Theory, Ser. B 80, 346--355 (2000; Zbl 1052.90067)] have developed, independently, combinatorial strongly polynomial algorithms to minimize submodular functions. These combinatorial algorithms perform multiplications and divisions, despite the problem of submodular function minimization does not involve multiplications nor divisions. Schrijver asked if one can minimize submodular functions in strongly polynomial time using only additions, subtractions, comparations, and the oracle calls for function values (this sort of algorithm is called fully combinatorial). In this paper, the author settles this problem by developing a fully combinatorial variant of the Iwate, Fleischer and Fujishige algorithm.