Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order

Niv Buchbinder, Moran Feldman, Siyue Liu +1

We study random order semi-streaming algorithms for submodular maximization under a wide range of combinatorial constraint classes, including matroids, matroid $p$-parity, $p$-exch…