Does greedy always find the best set?

No; the worked example gives a counterexample.

Does a budget constraint mean the same thing as a limit on item count?

Only when costs are uniform; general budgets change the feasible sets and relevant algorithms.

AI Glossary / Probabilistic machine learning / Intermediate

Submodular optimization

Definition

Submodular optimization seeks to minimize or maximize a set-valued objective with a diminishing-returns property. For a submodular function, adding an item to a smaller selected set provides at least as much marginal gain as adding the same item to a larger set containing it. This structure supports useful algorithms and approximation guarantees for many selection problems.

What it means

Suppose a team chooses examples, sensors, or representative documents. The first item covering a topic may be valuable, while another item covering almost the same topic contributes less. Submodularity formalizes that kind of overlap.

It is a property of the objective, not a synonym for any greedy selection process. Monotonicity is separate: a monotone objective never decreases when an item is added. A function can be submodular without being monotone. The optimization direction and constraints also matter; minimization, cardinality-constrained maximization, and budget-constrained maximization are different problems with different algorithms and guarantees.

How it works

Define a finite ground set of candidates and a function f assigning a value to each selected subset. For sets A contained in B and an item e outside B, compare f(A plus e) minus f(A) with f(B plus e) minus f(B). Submodularity requires the first difference to be at least the second.

For a normalized, nonnegative, monotone submodular objective with a limit of k items, the standard greedy algorithm repeatedly adds the item with the largest current marginal gain. With exact evaluations, its value is at least 1 minus 1/e, approximately 63.2 percent, of the optimal value under that cardinality constraint. This is a worst-case approximation guarantee, not a typical achieved percentage or a guarantee of exact optimality.

Other constraints, nonmonotone objectives, or approximate evaluations require suitable analyses and algorithms. Unconstrained submodular minimization has its own polynomial-time theory; the familiar greedy maximization guarantee should not be transferred to it.

Three practical examples

1. Representative records: select examples that cover different parts of a collection under a defined coverage or facility-location objective. Verify that the objective rewards the diversity relevant to the intended task.

2. Monitoring placement: choose locations whose detection coverage overlaps. Evaluate candidate sets against realistic scenarios and include installation constraints in the optimization formulation.

3. Document selection: assemble a limited set of passages covering important concepts while avoiding redundant coverage. Separately check factual accuracy and readability; maximizing a coverage score does not establish either.

Think of it this way

Think of collecting keys that open doors. The first key may open several doors, but a second key is less useful if most of its doors are already open. The gain depends on what the current collection covers. Submodularity captures that declining additional value when the coverage objective counts each door only once.

Worked example

Consider an original coverage problem with six topics and three candidate items. Item A covers topics {1, 2, 3, 4}; B covers {1, 2, 5}; C covers {3, 4, 6}. Let f(S) count the distinct topics covered by selected items, and allow at most two items.

Initially A has gain 4, while B and C each have gain 3. Greedy therefore selects A. After that, B adds only topic 5 and C adds only topic 6, so both have marginal gain 1. Break the tie in favor of B. The greedy set {A, B} covers five topics.

The alternative {B, C} covers all six topics, so it is optimal. The other pair, {A, C}, covers five. Greedy achieves 5 divided by 6, approximately 83.3 percent of the optimum in this example. It is not exact, despite the objective being monotone and submodular.

Diminishing returns can be seen directly for C: added to the empty set it contributes three topics; added after A it contributes only one. More generally, coverage is submodular because an item cannot uncover more new topics when the existing covered set grows. This example uses equal item costs and a count limit; unequal costs would require a different constraint treatment.

Illustrative case study

Fictional case: Maple Knowledge wants a small review set that represents its article archive. Analysts define a nonnegative coverage objective using an agreed topic inventory and a fixed number of articles. They compare greedy selection with exhaustive search on small subsets to verify the implementation and understand redundancy.

Editors then inspect whether selected articles accurately represent the covered topics. If the objective favors superficial mentions, the team changes its coverage definition rather than treating the approximation guarantee as proof of editorial quality. This fictional case illustrates objective design and validation without claiming a measured reduction in review effort.

Common misconceptions and mistakes

Diminishing returns is not the same as positive returns: submodularity alone does not imply monotonicity. A greedy algorithm does not prove an objective is submodular. The 63.2 percent guarantee needs its stated assumptions and concerns objective value, not probability of selecting the optimal set. Information-gain objectives are not automatically submodular in every probabilistic model; dependencies and conditional-independence assumptions can matter.

Business use

The practical value is a principled way to balance additional coverage against redundancy. The main risk is optimizing a convenient proxy that does not represent the business outcome. Teams should document the ground set, objective, costs, constraints, and any approximation assumptions. A theoretical guarantee applies to the modeled objective, so operational quality and unintended exclusions still require separate evaluation.

Check your understanding

Answer: 1.

Why does greedy choose A first?

Answer: Its initial coverage gain of four is largest.

Answer: 2.

Which two-item set is optimal?

Answer: B and C, which together cover all six topics.

Answer: 3.

What makes the objective submodular?

Answer: The marginal number of newly covered topics cannot increase as the selected set grows.

Related terms

Greedy algorithms
Diminishing returns
greedy algorithm
maximum coverage
facility location
marginal gain
approximation ratio
matroid constraint
cardinality constraint

Learn next

Verify diminishing returns on a small coverage function. Then compare greedy and exhaustive selection, distinguish monotonicity from submodularity, and study algorithms matched to cardinality, cost, or other feasibility constraints.

Sources

Krause and Golovin, Submodular Function Maximization, explains diminishing returns, coverage functions, greedy guarantees, and the importance of assumptions: https://las.inf.ethz.ch/files/krause12survey.pdf

The six-topic calculation and Maple Knowledge scenario are original teaching examples; the scenario is fictional.

Independent review consulted Definitions 1.2–1.3, coverage examples and Theorem 1.5 in the cited survey.

Previous: Subjectivity Next: Submodularity