multipass

• Streaming Submodular Maximization under Matroid Constraints

  ICALP 2022

  Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, Jan Vondrák, and Rico Zenklusen

  ---

  Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniques fail to give a similar understanding for natural generalizations, including matroid constraints. Our paper improves on the previously best approximation guarantees of $1/4$ and $1/2$ for single-pass and multi-pass streaming algorithms, respectively. In fact, our multi-pass streaming algorithm is tight in that any algorithm with a better guarantee than $1/2$ must make several passes through the stream and any algorithm that beats our guarantee of $1-1/e$ must make linearly many passes (as well as an exponential number of value oracle queries).

  submodular optimization streaming random order multipass

  [pdf]