A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions
| dc.creator | Iwata, Satoru | |
| dc.creator | Fleischer, Lisa | |
| dc.creator | Fujishige, Satoru | |
| dc.date | 2000-04-13 | |
| dc.date.accessioned | 2026-07-07T04:34:44Z | |
| dc.date.available | 2026-07-07T04:34:44Z | |
| dc.description | This paper presents the first combinatorial polynomial-time algorithm for minimizing submodular set functions, answering an open question posed in 1981 by Grotschel, Lovasz, and Schrijver. The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter. The resulting algorithm runs in time bounded by a polynomial in the size of the underlying set and the largest length of the function value. The paper also presents a strongly polynomial-time version that runs in time bounded by a polynomial in the size of the underlying set independent of the function value. | |
| dc.description | 17 pages | |
| dc.identifier | https://arxiv.org/abs/math/0004089 | |
| dc.identifier | http://arxiv.org/abs/math/0004089 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/59022 | |
| dc.subject | Combinatorics | |
| dc.title | A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions | |
| dc.type | text |