Submodular Optimization Reading Group
Spring 2015

See the Hackpad for discussions.

Sessions

• Thu, Feb. 12 (Thibaut): greedy algorithms for monotone submodular maximization under cardinality, knapsack and matroid constraints. [14, 11, 15] [notes]
• Tue, Feb. 17 (Jean): pipage rounding. [1] [notes]
• Tue, Feb. 24 (Jean): extensions (multilinear, concave closure), Poisson clocks, maximizing sum of weighted rank functions under matroid constraint. [3] [notes]
• Wed, Feb. 25 (Eric): continuous greedy algorithm, maximizing monotone submodular function under matroid constraint, submodular welfare problem. [16, 4] [notes]
• Thu, Mar. 05 (Bo): contention resolution schemes, non-monotone submodular maximization over independent set systems. [17] [notes]
• Thu, Mar. 12 (Thibaut): combinatorial algorithm for coverage (and submodular) maximization over a matroid. [8, 9, 10]
• Thu, Mar. 26 (Jean): unconstrainted non-monotone submodular maximization, random set, local search. [6] [notes]
• Thu, Apr. 02 (Eric): randomized, linear-time optimal unconstrained non-monotone submodular maximization. [2] [notes]
• Thu, Apr. 09 (Thibaut): non-monotone submodular maximization under matroid and knapsack constraints. [12]
• Thu, Apr. 23 (Jean): computational hardness of approximating set cover. [5, 7]
• Thu, Apr. 30 (Bo): information theoretic lower bound for welfare maximization. [13]

References

1. A. A. Ageev and M. Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Comb. Optim., 8(3):307–328, 2004. [pdf]
2. N. Buchbinder, M. Feldman, J. Naor, and R. Schwartz. A tight linear time (1/2)-approximation for unconstrained submodular maximization. In 53rd Annual IEEE Symposium on Foundations of Computer Science, (FOCS), pages 649–658, 2012. [pdf]
3. G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a submodular set function subject to a matroid constraint. In Integer programming and combinatorial optimization, pages 182–196. Springer, 2007. [pdf]
4. G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6):1740–1766, 2011. [pdf]
5. U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634–652, 1998. [pdf]
6. U. Feige, V. S. Mirrokni, and J. Vondrák. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4):1133–1153, 2011. [pdf]
7. Y. Filmus. Hardness of approximating set cover. January 2011. [pdf]
8. Y. Filmus and J. Ward. Maximum coverage over a matroid. In 29th Symposium on Theoretical Aspects of Computer Science (STACS), 2012. [pdf]
9. Y. Filmus and J. Ward. A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. In 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012. [pdf]
10. Y. Filmus and J. Ward. Monotone submodular maximization over a matroid via non-oblivious local search. SIAM Journal on Computing, 43:514–542, 2014. [pdf]
11. S. Khuller, A. Moss, and J. S. Naor. The budgeted maximum coverage problem. Information Processing Letters, 70(1):39–45, 1999. [pdf]
12. J. Lee, V. S. Mirrokni, V. Nagarajan, and M. Sviridenko. Non-monotone submodular maximization under matroid and knapsack constraints. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pages 323–332, 2009. [pdf]
13. V. Mirrokni, M. Schapira, and J. Vondrák. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In Proceedings of the 9th ACM conference on Electronic commerce, pages 70–77. ACM, 2008. [pdf]
14. G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions–i. Mathematical Programming, 14(1):265–294, 1978. [pdf]
15. M. Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41–43, 2004. [pdf]
16. J. Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 67–74. ACM, 2008. [pdf]
17. J. Vondrák, C. Chekuri, and R. Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 783–792. ACM, 2011. [pdf]

Last updated on Thu, Apr. 30 2015 at 10:53PM