A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization.

Niv Buchbinder, Moran Feldman, Joseph Naor, Roy Schwartz

Browse the full FOCS paper archive.