Submodular function

From Glossary

Jump to: navigation, search

Let LaTeX: N be a finite set and let LaTeX: f be a function on the subsets of LaTeX: N into LaTeX: \mathbb{R}. Then, LaTeX: f is submodular if it satisfies:

f(S \lor T) \le f(S) + f(T) - f(S \land T) \mbox{ for } S, T \subset N.

Example: LaTeX: \textstyle N=\{0,1\}^n (binary n-vectors) and LaTeX: \textstyle f(S) = \sum_{x \in S} \sum_{j=1}^{n} x_j. Instance: LaTeX: \textstyle n=2, LaTeX: \textstyle S=\{(0,1), (1,1)\}, LaTeX: \textstyle T=\{(1,0),(1,1)\}. Then, LaTeX: \textstyle f(S \lor T) = 4, LaTeX: \textstyle f(S)=3, LaTeX: \textstyle f(T)=3, LaTeX: \textstyle \mbox{and } f(S \land T) = 2. (The linearity of Sum makes the inequality hold with inequality.)

Personal tools