School of Technology and Computer Science Seminars

A Simple Combinatorial Algorithm for Submodular Function Minimization

by Mr. Sagnik Mukhopadhyay (School of Technology and Computer Science, TIFR)

Friday, July 13, 2012 from to (Asia/Kolkata)
at Colaba Campus ( A-212 (STCS Seminar Room) )
Description
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(n6.EO.lognM) 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