Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Optimal deletion-robust coreset for submodular maximization   In recent years we have witnessed an increase on the development of methods
for submodular optimization, which have been motivated by the wide
applicability of submodular functions in real-world data-science problems. In
this paper, we contribute to this line of work by considering the problem of
robust submodular maximization against unexpected deletions, which may occur
due to privacy issues or user preferences. Specifically, we study and derive
bounds for the minimum number of items a streaming algorithm has to remember,
in order to achieve a non-trivial approximation guarantee against adversarial
deletions up to $d$ items. We call the set of items that are kept by the
algorithm before adversarial deletions a deletion-robust coreset. We propose a
single-pass streaming algorithm that yields a
$(1-2\epsilon)/(4p)$-approximation for maximizing a non-decreasing submodular
function under a general $p$-matroid constraint and requires a coreset size $k
+ d/\epsilon$, where $k$ is the maximum size of a feasible solution. To the
best of our knowledge, this is the first work to achieve an (asymptotically)
optimal coreset size, as no constant approximation is possible with a coreset
of size sublinear in $d$.

31
The categories of this paper are: ao-sci
12
The categories of this paper are: nucl-th
28
The categories of this paper are: alg-geom
7
The categories of this paper are: hep-th
15
The categories of this paper are: nucl-ex
37
The categories of this paper are: supr-con
2
The categories of this paper are: math
27
The categories of this paper are: comp-gas
33
The categories of this paper are: plasm-ph
17
The categories of this paper are: q-fin
0
The categories of this paper are: hep-ph
5
The categories of this paper are: gr-qc
21
The categories of this paper are: adap-org
22
The categories of this paper are: chao-dyn
30
The categories of this paper are: q-alg
9
The categories of this paper are: nlin