Submodular functions

From cophywiki
Jump to: navigation, search

Introduction

Submodular functions play an important role in combinatorial optimization. A nice property of submodular functions is that minimizing over submodular functions can be done in polynomial time. We will give some examples for submodular functions, such as appropiately defined cut functions in directed (as well as in undirected) graphs. But first we give a formal definition of submodularity.

Definition (submodular)

Let E be a finite set, i.e. |E| <\ \infty. A function \textstyle f: 2^E \rightarrow \mathbb{R} is called submodular if and only if
f(A) + f(B)\ \ge\ f(A\ \cap\ B) + f(A\ \cup\ B)\,\!

for all subsets A,\ B\ \subseteq\ E.

Example 1

Let E = \{0,1\} and \textstyle f: 2^E \rightarrow \mathbb{R} with

f(\empty) = 0\,\! and f(\{0\}) = f(\{1\}) = f(\{E\}) = 1\,\!.

Then the function f is submodular.

Definition (supermodular)

A function \textstyle f: 2^E \rightarrow \mathbb{R} is called supermodular if and only if the function (-f) is submodular. If a function \textstyle f: 2^E \rightarrow \mathbb{R} is both submodular and supermodular, it is called modular.

In formulae, a function \textstyle f: 2^E \rightarrow \mathbb{R} is

supermodular if f(A) + f(B)\ \le\ f(A\ \cap\ B) + f(A\ \cup\ B)\,\!
modular if f(A) + f(B)\ =\  f(A\ \cap\ B) + f(A\ \cup\ B)\,\!

for all subsets A,\ B\ \subseteq E\,\!

Example 2

Let \textstyle w\ \in\ \mathbb{R^E} and \textstyle f: 2^E \rightarrow \mathbb{R} with  \textstyle f(\empty) = 0 and
\textstyle f(A) = \sum\limits_{e\ \in\ A} w_e for all subsets \textstyle A\ \subseteq\ E,\ A\ \ne\ \empty.

This function f is modular. In the special case of w_e = 1 for all e\ \in\ E we have

f(A) = |A| for all subsets A\ \subseteq\ E\,\!.
.

That is, the function value for a subset A equals the cardinality of A.


Example 3

Let G = (V,E) be a directed graph with node set V and edge set E. Further let

\delta^+(S) = \{(i,j)\ \in\ E:\ i\ \in\ S,\ j\ \notin\ S\}\,\!,
\delta^-(S) = \{(i,j)\ \in\ E:\ i\ \notin\ S,\ j\ \in\ S\}\,\! and
\delta(S) = \delta^+(S)\ \cup\ \delta^-(S)\,\!

for all node sets S\ \subseteq\ V. Let \textstyle w\ \in\ \mathbb{R_+^V}. Then the cut functions

f_+(S) = w(\delta^+(S)) = \sum\limits_{e\ \in\ \delta^+(S)} w_e\,\!,
f_-(S) = w(\delta^-(S)) = \sum\limits_{e\ \in\ \delta^-(S)} w_e\,\! and
f(S) = w(\delta(S)) = \sum\limits_{e\ \in\ \delta(S)} w_e\,\!

are submodular.