Submodular Optimization Reading Group
Spring 2015

See the Hackpad for discussions.

Sessions

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