|Time+Place:||Thursday 01/01/2015 14:30 Room 337-8 Taub Bld.|
|Title:||Aspects of Submodular Maximization Subject to a Matroid Constraint|
|Speaker:|| Moran Feldman - CS-Lecture
|| Affiliation: || School of Computer and Communication Sciences of EPFL
|| Host: || Seffi Naor
Submodular functions form a large natural class of set functions with applications in many fields including social networks, machine learning and game theory. Optimization of submodular functions subject to various constraints attracted much attention in recent years, both from theoretical and practical points of view. This talk considers the problem of maximizing a submodular function subject to a matroid constraint, which is a central problem demonstrating many of the modern approaches and techniques used in the field of submodular maximization. Many aspects of this problem have been studied, including its polynomial time approximability, fast (almost linear time) algorithms and online models. This talk surveys some of these aspects and explores a few of the main results obtained recently. Short Bio: Moran Feldman is a post-doctoral fellow at the School of Computer and Communication Sciences of EPFL. He obtained his B.A. and M.Sc. degrees from the Israeli Open University, and his Ph.D. from the Technion. During his graduate studies, Moran was a fellow of the Google European Fellowship in Market Algorithms and was awarded the Cisco prize. Additionally, he spent time, as an intern, in Yahoo! Research, Google and MSR. Moran's main research interests lie in the theory of algorithms. Many of his works are in the fields of submodular optimization and online computation.