A strongly polynomial-time algorithm for minimizing submodular functions

Satoru Iwata (), Lisa Fleischer () and Satoru Fujishige ()
Additional contact information
Satoru Iwata: Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka 560-8531, Japan
Lisa Fleischer: Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027, USA
Satoru Fujishige: Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka 560-8531, Japan

No 1999048, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: This paper presents a combinatorial polynomial-time algorithm for minimizing submolular set functions. 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 thescaled 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. These are the first combinatorial algorithms for submodular function minimization that run in (strongly) polynomial time.

Keywords: submodular function; combinatorial optimization; strongly polynomialtime algorithm. (search for similar items in EconPapers)
Date: 1999-07-01
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1999.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1999048

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().