Seminar Details
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
- Start Date: May 5, 2021
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Eric Balkanski - Columbia University
- Event Location: Online Event
- Event Additional Info: <p>The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://nam02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fsites.google.com%2Fview%2Fdimacs-theory-seminar%2Fhome&data=04%7C01%7Clindac%40dimacs.rutgers.edu%7C34e2fbbfea1344fcacc008d90f221617%7Cb92d2b234d35447093ff69aca6632ffe%7C1%7C0%7C637557461355858387%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=6Gdp4kqMAGGCy5DI%2FsluSTmLHcGop53lN3Mc%2FYEq7Jo%3D&reserved=0" style="text-decoration-line:none" target="_blank">https://sites.google.com/view/dimacs-theory-seminar/home</a></p>
- Presentation Type: Stand Alone Presentation
- Abstract:
The adaptive complexity model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Informally, the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially-many function evaluations in parallel. Since submodular optimization is regularly applied on large datasets we seek algorithms with low adaptivity to enable speedups via parallelization.
In this talk, I will discuss recent results that develop constant factor approximation algorithms for maximizing submodular functions under various constraints in the adaptive complexity model. I will focus on the problem of maximizing a monotone submodular function under a matroid constraint, for which we develop an algorithm that achieves an approximation guarantee that is arbitrarily close to the optimal 1 − 1/e approximation and has O(log(n) log(k)) adaptivity. This result is obtained using a novel technique of adaptive sequencing which departs from previous techniques for submodular maximization in the adaptive complexity model.
Joint work with Aviad Rubinstein and Yaron Singer.