Notes on greedy algorithms for submodular maximization

1 files changed, 98 insertions, 0 deletions

diff --git a/greedy/sub.bib b/greedy/sub.bib
new file mode 100644
index 0000000..5adbe9b
--- /dev/null
+++ b/greedy/sub.bib
@@ -0,0 +1,98 @@
+@book{fisher1978,
+  title={An analysis of approximations for maximizing submodular set functions—II},
+  author={Fisher, Marshall L and Nemhauser, George L and Wolsey, Laurence A},
+  year={1978},
+  publisher={Springer}
+}
+
+@article{nemhauser1978,
+  title={An analysis of approximations for maximizing submodular set functions—I},
+  author={Nemhauser, George L and Wolsey, Laurence A and Fisher, Marshall L},
+  journal={Mathematical Programming},
+  volume={14},
+  number={1},
+  pages={265--294},
+  year={1978},
+  publisher={Springer}
+}
+
+@article{edmonds1971,
+  title={Matroids and the greedy algorithm},
+  author={Edmonds, Jack},
+  journal={Mathematical programming},
+  volume={1},
+  number={1},
+  pages={127--136},
+  year={1971},
+  publisher={Springer}
+}
+
+@article{feige1998,
+  title={A threshold of ln n for approximating set cover},
+  author={Feige, Uriel},
+  journal={Journal of the ACM (JACM)},
+  volume={45},
+  number={4},
+  pages={634--652},
+  year={1998},
+  publisher={ACM}
+}
+
+@article{khuller1999,
+  title={The budgeted maximum coverage problem},
+  author={Khuller, Samir and Moss, Anna and Naor, Joseph Seffi},
+  journal={Information Processing Letters},
+  volume={70},
+  number={1},
+  pages={39--45},
+  year={1999},
+  publisher={Elsevier}
+}
+
+@article{sviridenko2004,
+  title={A note on maximizing a submodular set function subject to a knapsack constraint},
+  author={Sviridenko, Maxim},
+  journal={Operations Research Letters},
+  volume={32},
+  number={1},
+  pages={41--43},
+  year={2004},
+  publisher={Elsevier}
+}
+
+@incollection{calinescu2007,
+  title={Maximizing a submodular set function subject to a matroid constraint},
+  author={Calinescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan},
+  booktitle={Integer programming and combinatorial optimization},
+  pages={182--196},
+  year={2007},
+  publisher={Springer}
+}
+
+@inproceedings{filmus2012,
+  title={A tight combinatorial algorithm for submodular maximization subject to a matroid constraint},
+  author={Filmus, Yuval and Ward, Justin},
+  booktitle={Foundations of Computer Science (FOCS)},
+  pages={659--668},
+  year={2012},
+  organization={IEEE}
+}
+
+@inproceedings{vondrak2011,
+  title={Submodular function maximization via the multilinear relaxation and contention resolution schemes},
+  author={Vondr{\'a}k, Jan and Chekuri, Chandra and Zenklusen, Rico},
+  booktitle={Proceedings of the forty-third annual ACM symposium on Theory of computing},
+  pages={783--792},
+  year={2011},
+  organization={ACM}
+}
+
+@inproceedings{lin2010,
+  title={Multi-document summarization via budgeted maximization of submodular functions},
+  author={Lin, Hui and Bilmes, Jeff},
+  booktitle={Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics},
+  pages={912--920},
+  year={2010},
+  organization={Association for Computational Linguistics}
+}
+