A Simple Combinatorial Algorithm for Submodular Function Minimization

Speaker: 

Time: 

Friday, 13 July 2012, 15:00 to 16:30

Venue: 

Organisers: 

Submodular functions are important to study as they arise in many context as flow problems, game theoretic application etc. One important aspect to study about submodular function is the submodular function minimization. I will present an algorithm for minimizing integer valued submodular function. The algorithm runs in $O(n^6.EO.\log nM)$ time, where $n$ is cardinality of ground set, $M$ is maximum absolute value of the function, and $EO$ is the time for function evaluation.

Ref: Iwata S, Orlin J; A Simple Combinatorial Algorithm for Submodular Function Minimization; SODA 2009