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...

ver descrição completa

Detalhes bibliográficos

Publicado no:	Journal of the ACM 48, 4 (2001).
Autor principal:	Iwata, Satoru
Formato:	Artigo
Idioma:	English
Assuntos:	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.