A strongly polynomial-time algorithm for minimizing submodular functions

Iwata, Satoru;Fleischer, Lisa;Fujishige, Satoru
(1999)

Files

dp9948
  • Open Access
  • Unknown
  • 148.23 KB
Download

Details

Authors
  • Iwata, Satoru
    Author
  • Fleischer, Lisa
    Author
  • Fujishige, Satoru
    Author
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 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. These are the first combinatorial algorithms for submodular function minimization that run in (strongly) polynomial time.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Iwata, S., Fleischer, L., & Fujishige, S. (1999). A strongly polynomial-time algorithm for minimizing submodular functions (CORE Discussion Papers 1999/48). https://hdl.handle.net/2078.5/28804