Submodular set function: Difference between revisions

Revision as of 19:43, 25 November 2012

Revision as of 16:26, 28 November 2012

Line 29:

==== Asymmetric ====

A non-monotone submodular function which is not symmetric is called asymmetric.

For; example,Directed acuts directed graph cut is an asymmetric non-monotone submodular function.: 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>.

For example, a directed graph cut is an asymmetric non-monotone submodular function. 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 ==