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

Date Topic Presenter
Sept 27, 2019 Overview Talk Chaitanya Swamy
Oct 04, 2019 An Analysis of Approximations for Maximizing Submodular Set Functions by Fisher, Nemhauser and Wolsey Ishan Bansal
Oct 11, 2019 Maximizing a Monotone Submodular Function Subject to a Matroid Constraint by Calinescu, Gruia, Chekuri, Pál, and Vondrák Justin Toth
Oct 18, 2019 No Talk. Reading Week
Oct 25, 2019 Submodular Maximization over Multiple Matroids via Generalized Exchange Properties See also: this Akshay Ramachandran
Nov 01, 2019 Maximizing Non-Monotone Submodular Functions by Feige, Mirrokni, and Vondrák Zishen Qu
Nov 08, 2019 No talk volunteered. NA
Nov 15, 2019 Deterministic 0.5008-Approximation for Submodular Maximization over a Matroid by Buchbinder, Feldman, and Garg Ben Moore
Nov 22, 2019 Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes by Vondrák, Chekuri, and Zenklusen Sharat Ibrahimpur

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 (12)-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