A strongly polynomial-time algorithm for minimizing submodular functions

Preprint
Publisher Website
Google Scholar
    • preprint
      • Published in RePEc
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.

This publication has 0 references indexed in Scilit: