This is specifically talking about submodular function maximization problems. A submodular set function is a function f(S) that takes a set S and returns a "sco

This is specifically talking about submodular function maximization problems. A submodular set function is a function f(S) that takes a set S and returns a "score". The objective is to find the set S with the highest score. The "submodular" property means that f(S) has "diminishing returns", meaning roughly that each new element contributes less to the score as the set S gets bigger. It turns out that this is hard to maximize exactly, but the simplest possible greedy algorithm already achieves an impressive approximation ratio of 1 - 1/e. The downside is that even the fully greedy algorithm is still pretty slow if you need to find a large set S, which is what this paper is addressing with a parallelizable randomized algorithm. (It's not the first such algorithm, but it's apparently much faster than the previous state of the art.) [disclaimer: not an expert in any of this]