Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
This work advances the theory of streaming submodular optimization by providing the first random-order improvements for several constraint classes, benefiting algorithm designers in large-scale data processing.
The paper presents the first random order semi-streaming algorithms for submodular maximization under various constraints, achieving improved approximations over adversarial order. For matroids, they exponentially reduce the number of passes needed for a (1-1/e-ε)-approximation, showing a separation between adversarial and random order.
We study random order semi-streaming algorithms for submodular maximization under a wide range of combinatorial constraint classes, including matroids, matroid $p$-parity, $p$-exchange systems and $p$-systems. For most of these classes of constraints, our results are the first improvement over what is known to be achievable for adversarial order. For matroids, matching and $p$-matchoids, previous random order results were known, and we improve over some of these as well. In the case of matroids, our improved results show a separation between adversarial and random order semi-streaming algorithms, and exponentially improve the number of passes necessary for getting $1 - 1/e - \varepsilon$ approximation for maximizing a monotone submodular function subject to a matroid constraint. We also prove a new hardness result showing a similar separation for $p$-systems. Our results are based on two new technical tools. One tool provides a general way to translate offline algorithms for many classes of constraints into random order semi-streaming algorithms. The other tool is a semi-streaming variant of a recently proposed offline algorithm for matroid constraints.