|
3:30 pm, Seminar Hall Some topics in Submodular Optimization - a survey Dr. Sambuddha Roy IBM Research, New Delhi. 26-02-14 Abstract This survey talk will consider submodular function optimization. A submodular function $f$ is a set function such that for any sets $A$ and $B$, it holds that $f(A) + f(B) \geqs f(A \cup B) + f(A\cap B)$. Such functions are ubiquitous in computer science, economics etc.; for instance, they may be thought of as embodying the notion of ``diminishing returns''. One may also consider them as discrete analogues of \textit{convexity} (thus it has been fairly well-known that submodular functions can be minimized in polynomial time). Recent years have seen fascinating progress in this area, especially in the context of submodular function maximization subject to various constraints. This talk will discuss some exciting recent developments involving greedy algorithms in the context of submodular maximization.
|
