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) )
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 |