Tata Institute of Fundamental Research
A Simple Combinatorial Algorithm for Submodular Function Minimization
Student Seminar
Speaker:
Sagnik Mukhopadhyay
Organiser:
Sarat Babu Moka
Date:
Friday, 13 Jul 2012, 15:00 to 16:30
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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
| Speaker: | Sagnik Mukhopadhyay |
| Organiser: | Sarat Babu Moka |
| Date: | Friday, 13 Jul 2012, 15:00 to 16:30 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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
Ref: Iwata S, Orlin J; A Simple Combinatorial Algorithm for Submodular Function Minimization; SODA 2009