Submodular set function: Difference between revisions

Revision as of 05:57, 26 September 2012

Revision as of 19:34, 26 October 2012

Line 9:

A nonnegative submodular function is also a [[subadditive]] function, but a subadditive function need not be submodular.

==Applications==

==Types==

Line 41 ⟶ 39:

# Directed graph cuts

#:Let <math>\Omega=\{v_1,v_2,\dots,v_n\}</math> be the vertices of a [[directed 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>.

==Continuous extensions==

Line 76 ⟶ 73:

* [[Matroid]]

{{Div col end}}

==Citations==

Line 91 ⟶ 86:

==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=Satoru|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}}

==External links==

<!--- Categories --->