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
Claimed Submodular Function Maximization (Survey) by Krause and Golovin.
Claimed An Analysis of Approximations for Maximizing Submodular Set Functions by Fisher, Nemhauser and Wolsey.
Claimed Maximizing a Monotone Submodular Function Subject to a Matroid Constraint by Calinescu, Gruia, Chekuri, Pál, and Vondrák.
To be claimed Maximizing Submodular Set Functions Subject to Multiple Linear Constraints by Kulik, Ariel, Shachnai, and Tamir.
To be claimed Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature by Sviridenko, Vondrák, and Ward.
To be claimed Maximizing Nonmonotone Submodular Functions Under Matroid or Knapsack Constraints by Lee, Mirrokni, Nagarajan, and Sviridenko.
Claimed Maximizing Non-Monotone Submodular Functions by Feige, Uriel, Mirrokni, and Vondrák.
Claimed Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes by Vondrák, Chekuri, and Zenklusen.
To be claimed Symmetry and Approximability of Submodular Maximization Problems by Vondrák
To be claimed Constrained Submodular Maximization: Beyond 1/e by Ene and Nguyen.
To be claimed A Tight Linear Time (1⁄2)-Approximation For Unconstrained Submodular Maximization by Buchbinder, Feldman, Naor, Schwartz.
To be claimed The Adaptive Complexity of Maximizing a Submodular Function by Balkanski and Singer.
To be claimed Unconstrained Submodular Maximization with Constant Adaptive Complexity by Chen, Lin, Feldman, and Karbasi.
To be claimed Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond by Chekuri and Quanrud.
To be claimed Submodular Maximization with Matroid and Packing Constraints in Parallel by Ene, Nguyen, and Vladu.
To be claimed An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model by Balkanski, Rubinstein, and Singer.
To be claimed Non-Monotone Submodular Maximization in Exponentially Fewer Iterations by Balkanski, Breuer, and Singer.
Claimed Submodular Maximization over Multiple Matroids via Generalized Exchange Properties