Difference between revisions of "Submodular functions"

From cophywiki
Jump to: navigation, search
 
Line 4: Line 4:
 
<h3>Introduction</h3>
 
<h3>Introduction</h3>
 
Submodular functions play an important role in combinatorial optimization. A nice property of submodular functions is that minimizing over submodular functions can
 
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. For example appropiately defined cut functions in directed (as well as in undirected) graphs are submodular.
+
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.
 
But first we give a formal definition of submodularity.
  
Line 27: Line 27:
 
This function f is modular. In the special case of <math>w_e = 1</math> for all <math>e\ \in\ E</math> we have  
 
This function f is modular. In the special case of <math>w_e = 1</math> for all <math>e\ \in\ E</math> we have  
 
<blockquote><math>f(A) = |A|</math> for all subsets <math>A\ \subseteq\ E\,\!</math>.</blockquote>.
 
<blockquote><math>f(A) = |A|</math> for all subsets <math>A\ \subseteq\ E\,\!</math>.</blockquote>.
That is, the function value for a subset <math>A</math> equal the cardinality of <math>A</math>.
+
That is, the function value for a subset <math>A</math> equals the cardinality of <math>A</math>.
  
 
<!--
 
<!--

Latest revision as of 11:24, 28 April 2011

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.