  Two genres of heuristics that are frequently reported to perform much better
on "real-world" instances than in the worst case are greedy algorithms and
local search algorithms. In this paper, we systematically study these two types
of algorithms for the problem of maximizing a monotone submodular set function
subject to downward-closed feasibility constraints. We consider
perturbation-stable instances, in the sense of Bilu and Linial, and precisely
identify the stability threshold beyond which these algorithms are guaranteed
to recover the optimal solution. Byproducts of our work include the first
definition of perturbation-stability for non-additive objective functions, and
a resolution of the worst-case approximation guarantee of local search in
p-extendible systems.
