°Õ¾±³Ù±ô±ð:ÌýDeterministic Algorithms and Faster Algorithms for Submodular Maximization subject to a Matroid Constraint
| Speaker: | Niv Buchbinder |
| Affiliation: | Statistics and Operations Research at Tel Aviv university |
| Location: | MC 5501 |
´¡²ú²õ³Ù°ù²¹³¦³Ù:Ìý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.
Short bio: Niv Buchbinder is a professor in the department of Statistics and Operations Research at Tel Aviv university. He received his Ph.D. in Computer Science from the Technion, Israel in 2008, and then spent two years as a post-doctoral researcher at Microsoft Research, New England, MA. His primary research interests are algorithms for combinatorial optimization problems in offline and online settings.