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). |
|---|---|
| מחבר ראשי: | |
| פורמט: | Article |
| שפה: | English |
| נושאים: |