Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity

Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam +2

Streaming algorithms are generally judged by the quality of their solution, memory footprint, and computational complexity. In this paper, we study the problem of maximizing a mono…