A submodular function on a finite set 
is a real-valued function 
on its subsets
satisfying
 |
for every 
. This inequality
expresses diminishing marginal gains: the change from adding an element
outside a set is at least as large for a subset
as for the containing set (Bach 2013, p. 154). A normalized
function has 
, and a nondecreasing
function satisfies 
when 
. Matroid
rank is an integer-valued example. Polymatroids
use normalized nondecreasing submodular functions as capacity bounds.
