A set function is submodular when
for every . For finite , this is equivalent to diminishing returns:
The marginal increment of an element can only decrease as the surrounding set grows.[ref]
For necessity, apply the defining inequality to and . Conversely, enumerate and compare adding its elements to with adding them to . Summing the marginal inequalities gives .
A coverage function is an example: counts the covered objects in a finite universe. An added contributes only objects not already covered, so its gain decreases with . Entropy submodularity is another fundamental example.
For a set function with , sort the coordinates of as , and put . The Lovász extension is
Ties do not affect the result, because equal-coordinate terms telescope. At an indicator vector it gives , so it extends a discrete objective to a piecewise linear function on a vector space.
For when and zero otherwise, . More generally, the extension is a convex function exactly when is a submodular set function. This equivalence is what makes the construction useful: a diminishing-returns condition on subsets becomes a geometric property on real vectors.[ref]
A coverage function assigns a value to the union of objects covered by a selection. Let index sets in a finite universe . The unweighted version is
A weighted coverage function gives each a nonnegative weight and sums those weights over the same set union. Its value is zero on the empty selection and cannot decrease when more sets are selected.[ref]
The submodular set function property follows from an explicit marginal calculation:
If , the objects still uncovered after form a subset of those uncovered after . Nonnegative weights therefore make the gain no larger after : precisely the diminishing returns property.
For an original example, take , and weights . Then , and . The second set adds only three after the first, because their shared object is counted once. This models the value of distinct coverage, rather than the sum of overlapping collection sizes.
A weighted coverage function assigns nonnegative weights to members of a finite universe , lets each choice cover a subset , and values a selection by
An item covered twice is counted only once. If , and the weights are , then , and .
Its marginal gain of a set function is the total weight of newly covered items. As the selected set grows, fewer uncovered items remain, so the marginal gain of a set function can only decrease. This proves that a weighted coverage function is a monotone submodular set function. Nonnegative weights are essential to this argument. The construction models selecting sensors or experiments whose observations overlap.[ref]
Every real-valued submodular set function on a finite ground set is the sum of a normalised set function that is nonnegative, monotone and submodular, and a modular set function . A useful explicit choice is
Proof. The formula makes a modular set function, so is a submodular set function. It is a normalised set function because . For , diminishing returns gives , hence . Thus is a monotone set function, and starting at zero makes it a nonnegative function. The decomposition separates all potentially negative terminal marginal increments into the simple additive term. A constant term in is necessary unless is already a normalised set function.
Suppose is a normalised set function and a submodular set function, and cover every element of exactly times, counting repetitions in the indexed collection. Then the displayed inequality holds. Neither the monotone set function property nor the nonnegative function property is required.
Proof. Fix an ordering of and write for its successive marginal increments. The chain lower bound for a submodular set function gives . Summing counts each exactly times, and . Exact coverage matters because the may be negative. For a monotone set function, the same argument also allows each element to occur at least times.
Let be a normalised set function that is a submodular set function, and order a finite subset . Set and . Then the displayed inequality holds for every , with equality for . The right side is a modular set function lying below on the power set of and touching it at the top.
Proof. Reveal the elements of in the chosen order. Immediately before adding , the conditioning set is . By diminishing returns, its marginal increment is at least . Sum and use . The same telescoping sum gives equality at . The individual increments need not be nonnegative.
For a real-valued set function on a finite ground set, the displayed marginal increment comparison is equivalent to submodularity. The interpretation is that an additional item contributes no more after more items have already been chosen. This concerns relative increments, which may be negative; it does not assert the monotone set function property.
Proof. Applying the defining inequality for a submodular set function to and gives the comparison immediately. Conversely, list and compare adding these elements, in the same order, first to and then to . At every step the first conditioning set is contained in the second, so the first marginal increment is at least the second. The telescoping sums give
which rearranges to submodularity.

Ancestors (7)

  1. Set function
  2. Function
  3. Set theory
  4. Foundations of mathematics
  5. Area of mathematics
  6. Mathematics
  7. Home

Synonyms (1)

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (1)