# Difference between revisions of "Submodular functions"

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 | + | 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> | + | That is, the function value for a subset <math>A</math> equals the cardinality of <math>A</math>. |

<!-- | <!-- |

## Latest revision as of 12:24, 28 April 2011

## Contents

### 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 be a finite set, i.e. . A function is called*submodular*if and only if

for all subsets .

### Example 1

Let and with

and .

Then the function f is submodular.

### Definition (supermodular)

A function is called supermodular if and only if the function is submodular. If a function is both submodular and supermodular, it is called modular.In formulae, a function is

- supermodular if
- modular if

for all subsets

### Example 2

Let and with andfor all subsets .

This function f is modular. In the special case of for all we have

for all subsets ..

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

### Example 3

Let be a directed graph with node set and edge set . Further let

- ,
- and

for all node sets . Let . Then the cut functions

- ,
- and

are submodular.