Submodular set function: Difference between revisions

Revision as of 04:52, 1 March 2012

Revision as of 07:53, 19 March 2012

Line 27:

#:Let <math>\Omega=\{e_1,e_2,\dots,e_n\}</math> be the ground set on which a matroid is defined. Then the rank function of the matroid is a submodular function.

=== Non-monotone Submodular function===

A submodular function <math>f</math> which is not necessarily monotone is called as Non-monotone Submodular function.

====Symmetric Non-monotone Submodular function====

Line 91:

==References==

===General References===

*{{Citation|last=Schrijver|first=Alexander|year=2003|title=Combinatorial Optimization|___location=|publisher=[[Springer]]|isbn=35404438943-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= 05210101280-521-01012-8}}

*{{Citation|last=Fujishige|first=Saruto|year=2005|title=Submodular Functions and Optimization|___location=|publisher=[[Elsevier]]|isbn=04445208640-444-52086-4}}

*{{Citation|last=Narayanan|first=H.|year= 1997 |title=Submodular Functions and Electrical Networks|___location=|publisher=|isbn= 04448252310-444-82523-1}}

== External links ==