Interlaced Greedy Algorithm for Maximization of Submodular Functions in Nearly Linear Time

A deterministic approximation algorithm is presented for the maximization of non-monotone submodular functions over a ground set of size n subject to cardinality constraint k; the algorithm is based upon the idea of interlacing two greedy procedures.