A combinatorial strongly polynomial algorithm for minimizing submodular functions.

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.