The Technion Theory Lunch is a seminar run by the theory group at the Department of Computer Science, Technion. The seminar holds weekly meetings in which graduate students and faculty from the Technion and other universities in Israel and abroad present recent results or other interesting topics in theoretical computer science. The seminar is open to faculty, graduate and undergraduate students interested in theory of computing.
Wednesdays, 13:00-14:00 (food starts at 12:45)
Room 401, Taub Building
If you are interested in giving a talk at the seminar, contact Omri Ben-Eliezer and/or David Wajc.
The seminar’s mailing list is used to announce our weekly meetings, and also to publicize CS theory related events, such as workshops and seminars, in Israel and abroad.
To join or leave our mailing list.
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
Upcoming
