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

We study the problem of maximizing a submodular function subject to a matroid independence constraint. For more than two decades, a rich body of work has studied this problem using both discrete and continuous methods. We propose a novel hybrid approach based on a stochastic Poisson process that aims to combine the strengths of both discrete and continuous methods: it does not require discretization or rounding while performing very few single element operations.  Our approach matches the tight $ (1-\nicefrac{1}{e})$ approximation guarantee when the submodular function is monotone and achieves an approximation of $\nicefrac{1}{e}$ when the submodular function is non-monotone. We also present applications of our approach and obtain fast algorithms for various applications including submodular welfare maximization, and for the general and separable assignment problems.

Based on joint works with: Amit Ganz-Rozenman, Ariel Kulik, Thiago Oliveira and Mohit Singh