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.