Content deleted Content added
→Monotone Submodular function: fixed definition of a coverage function |
Disambiguated: graph → graph (mathematics), Springer → Springer Publishing; formatting: 4x whitespace, heading-style (using Advisor.js) |
||
Line 1:
<!-- Please leave this line alone! -->
In mathematics, '''submodular functions''' are set functions which usually appear in approximation algorithms, functions modeling user preferences in game theory. These functions have a natural diminishing returns property which makes them suitable for many applications.
==Definition==
Line 19:
#: Any function of the form <math>f(S)=\sum_{i\in S}w_i</math> is called a linear function. Additionally if <math>\forall i,w_i\geq 0</math> then f is monotone.
# Budget-additive functions
#: Any function of the form <math>f(S)=\min(B,\sum_{i\in S}w_i)</math> for each <math>w_i\geq 0</math> and <math>B\geq 0</math> is called budget additive.
# Coverage function
#:Let <math>\Omega=\{E_1,E_2,\ldots,E_n\}</math> be a collection of subsets of some ground set <math>\Omega'</math>. The function <math>f(S)=|\cup_{E_i\in S}E_i|</math> for <math>S\subseteq \Omega</math> is called a coverage function.
Line 33:
:Examples of Symmetric Non-Monotone Submodular function
# Graph cuts
#:Let <math>\Omega=\{v_1,v_2,\dots,v_n\}</math> be the vertices of a [[graph (mathematics)|graph]]. For any set of vertices <math>S\subseteq \Omega</math> let <math>f(S)</math> denote the number of edges <math>e=(u,v)</math> such that <math>u\in S</math> and <math>v\in \Omega-S</math>.
# [[Mutual information]]
#:Let <math>\Omega=\{X_1,X_2,\ldots,X_n\}</math> be a set of [[random variable]]s. Then for any <math>S\subseteq \Omega</math> we have that <math>f(S)=I(S;\Omega-S)</math> is a submodular function, where <math>I(S;\Omega-S)</math> is the mutual information.
Line 61:
==Optimization problems==
Submodular functions have properties which are very similar to convex and concave functions. Hence a lot of optimization problems can be cast as maximizing or minimizing submodular functions subject to various constraints.
# Minimization of submodular functions.
#: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 usually [[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.
Line 91:
==References==
===General References===
*{{Citation|last=Schrijver|first=Alexander|authorlink=Alexander Schrijver|year=2003|title=Combinatorial Optimization|___location=|publisher=[[Springer Publishing|Springer]]|isbn=3-540-44389-4}}
*{{Citation|last=Lee|first=Jon|authorlink=Jon Lee (mathematician)|year= 2004 |title=A First Course in Combinatorial Optimization |___location=|publisher=[[Cambridge University Press]]|isbn= 0-521-01012-8}}
*{{Citation|last=Fujishige|first=Saruto|year=2005|title=Submodular Functions and Optimization|___location=|publisher=[[Elsevier]]|isbn=0-444-52086-4}}
*{{Citation|last=Narayanan|first=H.|year= 1997 |title=Submodular Functions and Electrical Networks|___location=|publisher=|isbn= 0-444-82523-1}}
==
| |||