אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Maximization of submodular functions under various constraints is a fundamental problem that has been studied extensively.
In this talk I will discuss submodular functions and interesting research questions in the field.
I will present several new techniques that lead to both deterministic algorithms and faster randomized algorithms for maximizing submodular functions.
In particular, for monotone submodular functions subject to a matroid constraint we design a deterministic non-oblivious local search algorithm that has an approximation guarantee of 1 – 1/e – \eps (for any \eps > 0), vastly improving over the previous state-of-the-art 0.5008-approximation.
For general (non-monotone) submodular functions we introduce a new tool, that we refer to as the extended multilinear extension, designed to derandomize submodular maximization algorithms that are based on the successful “solve fractionally and then round” approach.