Budget-Smoothed Analysis for Submodular Maximization

The greedy algorithm for submodular function maximization subject to cardinality constraint is guaranteed to approximate the optimal solution to within a $1-1/e$ factor. For worst-case instances, it is well known that this guarantee is essentially tight -- for greedy and in fact any efficient algorithm. Motivated by the question of why greedy performs better in practice, we introduce a new notion of budget smoothed analysis. Our framework requires larger perturbations of budgets than traditional smoothed analysis for e.g. linear programming. Nevertheless, we show that under realistic budget distributions, greedy and related algorithms enjoy provably better approximation guarantees, that hold even for worst-case submodular functions.