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 up to τ elements from the chosen set. For the fundamental case of τ = 1, we give a deterministic (1 − 1/e) − Ω(1/m) approximation, which makes O(n m+1 ) queries. In the process, we develop a deterministic (1 − 1/e) − Ω(1/m) approximate greedy algorithm for bi-objective maximization of (two) monotone submodular functions. Generalizing the ideas and using a result from Chekuri et al. (2010), we show a randomized (1 − 1/e) − ǫ approximation for constant τ and we give a fast and practical 0.387 algorithm. Finally, we also give a result for a more general setting.
For the special case of cardinality constraint (which will be our focus here), REF recently showed that the greedy algorithm can be generalized to achieve a deterministic 1 − 1/e − approximation for the special case of bi-objective maximization.
Robust Monotone Submodular Function Maximization
IPCO
Mathematics Computer Science