@inproceedings{f01e57a1b8e149e38c5b66ea54a33b83,
title = "Robust monotone submodular function maximization",
abstract = "We consider a robust formulation, introduced by Krause et al. (2008), of the classic cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w.r.t. adversarial removal of a given number of elements from the chosen set. In particular, for the fundamental case of single element removal, we show that one can approximate the problem up to a factor (1−1/e)−ϵ by making O(n 1/ϵ) queries, for arbitrary ϵ > 0. The ideas are also extended to more general settings.",
author = "Orlin, {James B.} and Schulz, {Andreas S.} and Rajan Udwani",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 18th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2016 ; Conference date: 01-06-2016 Through 03-06-2016",
year = "2016",
doi = "10.1007/978-3-319-33461-5_26",
language = "English",
isbn = "9783319334608",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "312--324",
editor = "Martin Skutella and Quentin Louveaux",
booktitle = "Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Proceedings",
}