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
|
@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}
}
|
