Submodular set function

In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory (as functions modeling user preferences) and electrical networks. Recently, submodular functions have also found immense utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains. If Ω {displaystyle Omega } is a finite set, a submodular function is a set function f : 2 Ω → R {displaystyle f:2^{Omega } ightarrow mathbb {R} } , where 2 Ω {displaystyle 2^{Omega }} denotes the power set of Ω {displaystyle Omega } , which satisfies one of the following equivalent conditions. A nonnegative submodular function is also a subadditive function, but a subadditive function need not be submodular.If Ω {displaystyle Omega } is not assumed finite, then the above conditions are not equivalent. In particular a function f {displaystyle f} defined by f ( S ) = 1 {displaystyle f(S)=1} if S {displaystyle S} is finite and f ( S ) = 0 {displaystyle f(S)=0} if S {displaystyle S} is infinite satisfies the first condition above, but the second condition fails when S {displaystyle S} and T {displaystyle T} are infinite sets with finite intersection. A submodular function f {displaystyle f} is monotone if for every T ⊆ S {displaystyle Tsubseteq S} we have that f ( T ) ≤ f ( S ) {displaystyle f(T)leq f(S)} . Examples of monotone submodular functions include: A submodular function which is not monotone is called non-monotone. A non-monotone submodular function f {displaystyle f} is called symmetric if for every S ⊆ Ω {displaystyle Ssubseteq Omega } we have that f ( S ) = f ( Ω − S ) {displaystyle f(S)=f(Omega -S)} .Examples of symmetric non-monotone submodular functions include: