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 http://theory.epfl.ch/moranfe/
Affiliation: School of Computer and Communication Sciences of EPFL
Host: Seffi Naor

Abstract:

 
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.