Maximization of a submodular function is NP-hard even for a simple cardinality constraint, and so several approaches for approximation have been considered. Classical techniques for maximizing submodular functions under various types of constraints fall broadly into two paradigms: greedy and local-search techniques. The greedy algorithm, that incrementally constructs a solution by choosing the most valuable element at each iteration, provides a \((1 - e^{-1})\) -approximation for a cardinality constraint (i.e. a uniform matroid). This is known to be the best-possible, both under the assumption that \(P \ne NP\)  and in the model in which the algorithm may only access the function \(f\)  by making (a polynomial number of) value queries [1]}, [2]}. For a general matroid constraint, the greedy algorithm attains only \(1/2\) -approximation [3]}, but Calinescu et al. [4]} obtained a \((1 - e^{-1})\) -approximation algorithm via the continuous greedy algorithm. For more complex constraints, the best known guarantees are provided by local search algorithms [5]}, [6]}, [7]}, which iteratively improve a current solution by repeated, relatively small exchanges.
