Streaming Submodular Maximization Under Matroid Constraints

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. This paper aims at closing this gap. For a single matroid of rank k (i.e., any solution has cardinality at most k), our main results are a single-pass streaming algorithm that uses [Formula: see text] memory and achieves an approximation guarantee of 0.3178 and a multipass streaming algorithm that uses [Formula: see text] memory and achieves an approximation guarantee of [Formula: see text] by taking a constant (depending on ε) number of passes over the stream. This improves on the previously best approximation guarantees of 1/4 and 1/2 for single-pass and multipass streaming algorithms, respectively. In fact, our multipass 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 [Formula: see text] must make linearly many passes (as well as an exponential number of value oracle queries). Moreover, we show how the approach that we use for multipass streaming can be further strengthened if the elements of the stream arrive in uniformly random order, implying an improved result for p-matchoid constraints. Funding: This research was supported by the Israel Science Foundation [Grants 1357/16 and 459/20] and NCCR—on the Move [Grants 200021_184622 and 200021_184656]. This project also received funding from the European Research Council [Grant 817750] under the European Union’s Horizon 2020 Research and Innovation Programme.