1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
@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{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}
}
@book{schrijver2003,
title={Combinatorial optimization: polyhedra and efficiency},
author={Schrijver, Alexander},
volume={24},
year={2003},
publisher={Springer}
}
@article{calinescu2011,
title={Maximizing a monotone submodular function subject to a matroid constraint},
author={Calinescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan},
journal={SIAM Journal on Computing},
volume={40},
number={6},
pages={1740--1766},
year={2011},
publisher={SIAM}
}
@article{ageev2004,
author = {Alexander A. Ageev and
Maxim Sviridenko},
title = {Pipage Rounding: {A} New Method of Constructing Algorithms with Proven
Performance Guarantee},
journal = {J. Comb. Optim.},
volume = {8},
number = {3},
pages = {307--328},
year = {2004},
timestamp = {Sun, 15 Nov 4434325 05:30:56 +},
biburl = {http://dblp.uni-trier.de/rec/bib/journals/jco/AgeevS04},
bibsource = {dblp computer science bibliography, http://dblp.org}
}
@inproceedings{vondrak2008,
title={Optimal approximation for the submodular welfare problem in the value oracle model},
author={Vondr{\'a}k, Jan},
booktitle={Proceedings of the fortieth annual ACM symposium on Theory of computing},
pages={67--74},
year={2008},
organization={ACM}
}
@inproceedings{filmus2012,
author = {Yuval Filmus and Justin Ward},
title = {Maximum coverage over a matroid},
booktitle = {29th Symposium on Theoretical Aspects of Computer Science ({STACS} 2012)},
year = {2012}
}
@inproceedings{filmus2012tight,
author = {Yuval Filmus and Justin Ward},
title = {A tight combinatorial algorithm for submodular maximization subject to a matroid constraint},
booktitle = {53rd Annual {IEEE} Symposium on Foundations of Computer Science ({FOCS} 2012)},
year = {2012}
}
@article{filmus2014,
author = {Yuval Filmus and Justin Ward},
title = {Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search},
journal = {SIAM Journal on Computing},
volume = {43},
issue = {2},
year = {2014},
pages = {514--542}
}
|
