Submodular set function optimization includes maximizing or minimizing a submodular function with or without some constraints. One of the directions is non-monotone submodular maximization without constraint. This problem is, given a non-negative submodular set function \(f\) , to find a subset \(S\)  that maximizes \(f(S)\) . Since this problem captures many applications in machine learning, viral marketing, etc., it has been studied extensively. A deterministic local search gives a \(1/3\)  -approximation and a randomized smoothed local search algorithm gives \(2/5\) -approximation [1]}. Buchbinder et al. further improve that result, they show that a deterministic double greedy algorithm provides 1/3-approximation, and the randomized version of it gives a 1/2-approximation, both in linear time [2]}.
