Submodular set function: Difference between revisions

Revision as of 07:53, 19 March 2012

Revision as of 06:50, 26 March 2012

Line 65:

#:Under the simplest case the problem is to find set <math>S\subseteq \Omega</math> which minimizes submodular function subject to no constraints. A series of results <ref name="GLS" /><ref name="Cunningham" /><ref name="IFF" /><ref name="Schrijver" /> have established the polynomial time solvability of this problem. Finding [[minimum cut]] in a graph is a special case of this problem.

# Maximization of submodular functions.

#:Unlike minimization, maximization of submodular functions is typicallyusually [[NP-hard]]. A host of problems such as [[max cut]], [[maximum coverage problem]] can be cast as special cases of this problem under suitable constraints. Typically the approximation algorithms for these problems are based on either greedy or local search type of algorithms.

## Maximizing a Symmetric Non-monotone Submodular function subject to no constraint. This problem admits a 1/2 approximation algorithm<ref name="FMV" />. Finding [[max cut]] is a special case of this problem.

## Maximizing a Monotone Submodular function subject to cardinality constraint. This problem admits a 1-1/e approximation algorithm<ref name="NVF" />. [[Maximum coverage problem]] is a special case of this problem.