Submodular Optimization: Diminishing Returns with Guarantees

Choosing the best subset under a budget is usually intractable, unless the objective has diminishing returns. That property is submodularity, and it turns hard selection problems into ones a simple greedy algorithm solves near-optimally. This path builds it from the definition and its convexity analogy, through the celebrated (1 - 1/e) guarantee of Nemhauser, Wolsey, and Fisher, to sensor placement, influence maximization, and summarization, and finally the wider landscape of minimization and non-monotone problems.