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

Полное описание

Библиографические подробности

Опубликовано в::	Journal of the ACM 48, 4 (2001).
Главный автор:	Iwata, Satoru
Формат:	Статья
Язык:	English
Предметы:	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.