Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints

Chien-Chung Huang, Theophile Thiery, Justin Ward

We give improved multi-pass streaming algorithms for the problem of maximizing a monotone or arbitrary non-negative submodular function subject to a general $p$-matchoid constraint…