submodularity

Submodularity is a property of set functions that formalizes the idea of diminishing returns. It is a central concept in combinatorial optimization with applications across computer science, economics, and data science.

Formally, let N be a finite ground set and f: 2^N -> R a real-valued function on subsets of N. f is submodular if for all A ⊆ B ⊆ N and all e ∉ B, the inequality f(A ∪ {e}) − f(A) ≥ f(B ∪ {e}) − f(B) holds. Equivalently, for all A,B ⊆ N, f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B). Submodular functions exhibit diminishing marginal gains: adding an element later yields at most the same gain as adding it earlier. Submodularity can occur with monotone (nondecreasing) or non-monotone functions.

Common examples include: the cut function in a graph, where f(S) counts edges between S and its complement; the coverage or set-covering function, where f(S) measures the number of elements covered by sets indexed by S; the entropy H(X_S) of a collection of random variables, which is submodular; and the rank function of a matroid, which is submodular.

Optimization aspects are a key reason for interest. Submodular function minimization is solvable in polynomial time, though with complex algorithms. Submodular maximization is generally NP-hard, but good approximation guarantees exist: the greedy algorithm achieves a (1 − 1/e) approximation for monotone submodular maximization under a cardinality constraint, and similar guarantees extend to broader constraints with appropriate techniques.

Applications abound in machine learning, sensor placement, data summarization, influence maximization, and economics. Submodularity provides a principled framework for designing scalable, theoretically grounded optimization methods.