
The offline LazyGreedy algorithm [1]}, which is both theoretically optimal and obtains the same solution as greedy (in faster time). Note that we don't expect to outperform it with a streaming algorithm; but as we hoped, our algorithm comes close.

The SieveStreaming algorithm of Badanidiyuru et al. [2]}, which is the first algorithm to appear for adversarial streaming submodular optimization.

The Salsa algorithm of Norouzi-Fard et al. [3]}, which is the first “beyond \(1/2\) " approximation algorithm for random-order streams. This algorithm runs several varients of SieveStreaming in parallel with thresholds that change as the algorithm progresses through the stream.
SieveStreaming is also known as threshold greedy in the literature [4]}. Note that the later SieveStreaming++ algorithm of [5]} is more efficient, but for approximation ratio SieveStreaming is a stronger benchmark.
for adversarial order streaming. As we would expect, our algorithm performs better on random arrival streams.

