Submodular set function: Difference between revisions

Revision as of 01:30, 25 October 2011

Revision as of 02:05, 25 October 2011

Line 4:

==Definition==

'''Submodular function''' is a set function <math>f:2^{\Omega}\rightarrow R</math> which satisfies one of the following ''equivalent'' definitions<ref>{{Harvard citations|last name="SchrijverBook" Schrijver|year = 2003|loc = §44, p. 766|nb = }}</ref> definitions.

# For every <math>X\subseteq Y\subseteq \Omega</math> and <math>x\in \Omega\backslash Y</math> we have that <math>f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)</math>

# For every <math>S,T\subseteq \Omega</math> we have that <math>f(S)+f(T)\geq f(S\cup T)+f(S\cap T)</math>

Line 60:

## Maximizing a Montone 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.

==ReferencesSee also==

{{Div col|cols=1}}

* [[Supermodular function]]

* [[Polymatroid]]

* [[Matroid]]

{{Div col end}}

==Citations==

{{reflist|

refs=

<ref name="SchrijverBook">Alexander Schrijver. Combinatorial Optimization, Polyhedra and Efficiency. Springer. ISBN-13: 978-3540443896 </ref>

<ref name="GLS">M. Grotschel, L. Lovasz, and A. Schrijver , The ellipsoid method and its consequences in combinatorial optimization,Combinatorica,1 (1981),pp. 169–197.</ref>

<ref name="Cunningham">W. H. Cunningham, On submodular function minimization, Combinatorica,5 (1985),pp. 185–192.</ref>

Line 71 ⟶ 79:

<ref name="NVF"> G. L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I, Mathematical Programming 14 (1978), 265–294</ref>

}}

==References==

===General References===

*{{Citation|last=Schrijver|first=Alexander|year=2003|title=Combinatorial Optimization|___location=|publisher=[[Springer]]|isbn=3540443894}}

*{{Citation|last=Lee|first=Jon|year= 2004 |title=A First Course in Combinatorial Optimization |___location=|publisher=[[Cambridge University Press]]|isbn= 0521010128}}

*{{Citation|last=Fujishige|first=Saruto|year=2005|title=Submodular Functions and Optimization|___location=|publisher=[[Elsevier]]|isbn=0444520864}}

*{{Citation|last=Narayanan|first=H.|year= 1997 |title=Submodular Functions and Electrical Networks|___location=|publisher=|isbn= 0444825231}}

Line 84 ⟶ 93:

<!--- Categories --->

[[Category:Combinatorial optimization| ]]

[[Category:Approximation algorithms| ]]