Authors 
: 

Document type 
: 
Document de travail (Working Paper) 
Abstract 
: 
This paper presents a combinatorial polynomialtime 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 polynomialtime 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. 
Publication date 
: 
1999 
Collection 
: 
CORE Discussion Papers  1999/48 
Affiliation 
: 
UCL
 CORE  Center for Operations Research and Econometrics

Keywords 
: 
Submodular function ; Combinatorial optimization ; Strongly polynomialtime algorithm

Links 
: 
