Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Robust Monotone Submodular Function Maximization   We consider a robust formulation, introduced by Krause et al. (2008), of the
classical 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 $\tau$ elements
from the chosen set. For the fundamental case of $\tau=1$, we give a
deterministic $(1-1/e)-1/\Theta(m)$ approximation algorithm, where $m$ is an
input parameter and number of queries scale as $O(n^{m+1})$. In the process, we
develop a deterministic $(1-1/e)-1/\Theta(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)-\epsilon$ approximation for constant $\tau$ and $\epsilon\leq
\frac{1}{\tilde{\Omega}(\tau)}$, making $O(n^{1/\epsilon^3})$ queries. Further,
for $\tau\ll \sqrt{k}$, we give a fast and practical 0.387 algorithm. Finally,
we also give a black box result result for the much more general setting of
robust maximization subject to an Independence System.

36
The categories of this paper are: cmp-lg
19
The categories of this paper are: eess
14
The categories of this paper are: math-ph
18
The categories of this paper are: econ
6
The categories of this paper are: astro-ph
11
The categories of this paper are: hep-lat
5
The categories of this paper are: gr-qc
24
The categories of this paper are: dg-ga
20
The categories of this paper are: acc-phys
37
The categories of this paper are: supr-con
25
The categories of this paper are: patt-sol
0
The categories of this paper are: hep-ph
21
The categories of this paper are: adap-org
7
The categories of this paper are: hep-th
30
The categories of this paper are: q-alg
3
The categories of this paper are: physics