Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel

Yixin Chen, Tonmoy Dey, Alan Kuhnle

For the problem of maximizing a monotone, submodular function with respect to a cardinality constraint $k$ on a ground set of size $n$, we provide an algorithm that achieves the st…