  The greedy algorithm for monotone submodular function maximization subject to
cardinality constraint is guaranteed to approximate the optimal solution to
within a $1-1/e$ factor. Although it is well known that this guarantee is
essentially tight in the worst case -- for greedy and in fact any efficient
algorithm, experiments show that greedy performs better in practice. We observe
that for many applications in practice, the empirical distribution of the
budgets (i.e., cardinality constraints) is supported on a wide range, and
moreover, all the existing hardness results in theory break under a large
perturbation of the budget.
  To understand the effect of the budget from both algorithmic and hardness
perspectives, we introduce a new notion of budget smoothed analysis. We prove
that greedy is optimal for every budget distribution, and we give a
characterization for the worst-case submodular functions. Based on these
results, we show that on the algorithmic side, under realistic budget
distributions, greedy and related algorithms enjoy provably better
approximation guarantees, that hold even for worst-case functions, and on the
hardness side, there exist hard functions that are fairly robust to all the
budget distributions.
