When Greedy Algorithms are Good Enough

[vit_tucek]

A proof that in quite a general situation a monotonic submodular function on subsets of a set X guarantees that the greedy algorithm finds k-element subset of X within (1-1/e) of the maximum among the k-element subsets. There is a nice review of extensions and generalizations of this problem in the last section.

http://jeremykun.com/2014/07/07/when-greedy-algorithms-are-good-enough-submodularity-and-the-1-1e-approximation/