Submodular Function Maximization

This term our reading group studies the broad topic of submodular function maximization, with a special focus on the emerging adaptive complexity model.

If you are interested in presenting please fill out this form.

Schedule

Suggested Papers

1. Claimed Submodular Function Maximization (Survey) by Krause and Golovin.

2. Claimed An Analysis of Approximations for Maximizing Submodular Set Functions by Fisher, Nemhauser and Wolsey.

3. Claimed Maximizing a Monotone Submodular Function Subject to a Matroid Constraint by Calinescu, Gruia, Chekuri, Pál, and Vondrák.

4. To be claimed Maximizing Submodular Set Functions Subject to Multiple Linear Constraints by Kulik, Ariel, Shachnai, and Tamir.

5. To be claimed Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature by Sviridenko, Vondrák, and Ward.

6. To be claimed Maximizing Nonmonotone Submodular Functions Under Matroid or Knapsack Constraints by Lee, Mirrokni, Nagarajan, and Sviridenko.

7. Claimed Maximizing Non-Monotone Submodular Functions by Feige, Uriel, Mirrokni, and Vondrák.

8. Claimed Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes by Vondrák, Chekuri, and Zenklusen.

9. To be claimed Symmetry and Approximability of Submodular Maximization Problems by Vondrák

10. To be claimed Constrained Submodular Maximization: Beyond 1/e by Ene and Nguyen.

11. To be claimed A Tight Linear Time (1/2)-Approximation For Unconstrained Submodular Maximization by Buchbinder, Feldman, Naor, Schwartz.

12. To be claimed The Adaptive Complexity of Maximizing a Submodular Function by Balkanski and Singer.

13. To be claimed Unconstrained Submodular Maximization with Constant Adaptive Complexity by Chen, Lin, Feldman, and Karbasi.

14. To be claimed Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond by Chekuri and Quanrud.

15. To be claimed Submodular Maximization with Matroid and Packing Constraints in Parallel by Ene, Nguyen, and Vladu.

16. To be claimed An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model by Balkanski, Rubinstein, and Singer.

17. To be claimed Non-Monotone Submodular Maximization in Exponentially Fewer Iterations by Balkanski, Breuer, and Singer.

18. Claimed Deterministic 0.5008-Approximation for Submodular Maximization over a Matroid (Buchbinder, Feldman, and Garg)

19. Claimed Submodular Maximization over Multiple Matroids via Generalized Exchange Properties