Timezone: »

 
Poster
Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach
Slobodan Mitrovic · Ilija Bogunovic · Ashkan Norouzi-Fard · Jakub M Tarnawski · Volkan Cevher

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #155
in Posters Wed »

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 are removed after the stream is finished. We develop a 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.

Keywords: Submodular Optimization · Applications
[ Paper] 

Author Information

Slobodan Mitrovic (EPFL)

I am doing PhD in theoretical computer science. My research interests orbit around graph theory and combinatorial optimization.

Ilija Bogunovic (EPFL Lausanne)
Ashkan Norouzi-Fard (EPFL)
Jakub M Tarnawski (EPFL)
Volkan Cevher (EPFL)

More from the Same Authors