Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach
We study the classical problem of maximizing a monotone submodular function subject to a cardinality constraint k, with two additional twists: (i) elements arrive in a streaming fashion and (ii) m items from the algorithm’s memory might be removed after the stream is finished. We develop the first robust submodular algorithm STAR-T. It is based on a novel partitioning structure and an exponentially decreasing thresholding rule. STAR-T makes one pass over the data and retains a short but robust summary. We show that after the removal of any m elements from the obtained summary, a simple greedy algorithm STAR-T-GREEDY that runs on the remaining elements achieves a constant-factor approximation guarantee. In two different data summarization tasks, we demonstrate that it matches or outperforms existing greedy and streaming methods, even if they are allowed the benefit of knowing the removed subset in advance.
7042_1-streaming-robust-submodular-maximizationa-partitioned-thresholding-approach.pdf
openaccess
2.19 MB
Adobe PDF
92ef9e7e1c9027b20eb669a8e6d7f86c
supplementary-material.pdf
openaccess
276.02 KB
Adobe PDF
adb365d224f70661b40b1cd0e1cf49a5