*F()*mapping a subset of a finite set

*V*to a real number has the following property.

*A*and

*B, F(A) + F(B) >= F(A U B) + F(A ^ B)*, where AUB and A^B are union and intersection.

A more significant definition is that for any subsets S and *R*, *S* is a subset of *R*, an element *e* in *V*, *F(S U {e}) – F(S) >= F(R U {e}) -F(R). *HereĀ *F(S U {e}) – F(S) *can be considered as the marginal value of *e* with respect to *S*.

If *-F()* is submodular, then *F()* is called supermudular.

If *F()* is both submodular and supermodular, *F()* is called modular.

Several examples of submodular function.

For a graph *G(V,E)*, define *F(A)* on a subset of *V* to be the number of edges in the subgraph induced by *A*.

For a directed graph *G(V,E)* and two vertices *s* and *t*, define *F(A)* on a subset of *V/{s,t}* to be the number of cut edges between *AU{s}* and *(V-A)U{t}*.

There are some greedy algorithms to optimize a submodular function.