Archive for December, 2008

Submodular Functions

A submodular function F() mapping a subset of a finite set V to a real number has the following property.

For any subsets 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.


Read Full Post »