Group:Algorithms, Complexity and Cryptography Group
Title: Optimization submodular functions
Speaker: Jian Li University
Time: 2011-12-09 14:00-2011-12-09 15:30
Venue: FIT 1-222

Abstract:

I will give a brief introduction to submodular functions and related concepts, and survey some of recent results in optimizing submodular functions (under various constraints). I will go into the details of one recent remarkable result about maximizing submodular function under matroid constraints (the 1-1/e approx. using continuous greedy+pipage round method).