Submodular maximization is indeed NP-complete, but we can find approximate solutions in polynomial time. This paper speeds up the parallel running time of the a

Submodular maximization is indeed NP-complete, but we can find approximate solutions in polynomial time. This paper speeds up the parallel running time of the approximation from O(n) to O(log n), meaning that they've found a way to make the algorithm more parallelizable, though you still have to do the same amount of work.