Submodular set function: Difference between revisions

Revision as of 14:19, 10 January 2013

Revision as of 19:38, 10 January 2013

Line 2:

== Definition ==

If <math>\Omega</math> is a [[set (mathematics)|set]], a submodular function is a set function <math>f:2^{\Omega}\rightarrow \mathbb{R}</math>, where <math>2^\Omega</math> denotes the [[Power set#Representing subsets as functions|power set]] of <math>\Omega</math>, which satisfies one of the following equivalent definitions.<ref>{{Harvard citations|last = Schrijver|year = 2003|loc = §44, p. 766|nb = }}</ref>.

# For every <math>X, Y \subseteq \Omega</math> with <math> X \subseteq Y</math> and every <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 10:

== Types of submodular functions ==

=== Monotone ===

A submodular function <math>f</math> is ''monotone'' if for every <math>T\subseteq S</math> we have that <math>f(T)\leq f(S)</math>. Examples of monotone submodular functions include:

Line 32 ⟶ 33:

== Continuous extensions ==

=== Lovász extension ===

This extension is named after mathematician [[László Lovász]]. Consider any vector <math>\bold{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the Lovász extension is defined as <math>f^L(\bold{x})=\mathbb{E}(f(\{i|x_i\geq \lambda\}))</math> where the expectation is over <math>\lambda</math> chosen from the [[uniform distribution (continuous)|uniform distribution]] on the interval <math>[0,1]</math>. The Lovász extension is a convex function.

Line 64 ⟶ 66:

<ref name="GLS">M. Gr&ouml;tschel, [[László Lovász|L. Lovasz]] and [[Alexander Schrijver|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>

<ref name="IFF"> S. Iwata, L. Fleischer, and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, J. ACM 48 (2001), pp. 761–777.</ref>

<ref name="Schrijver">[[Alexander Schrijver|A. Schrijver]], A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B 80 (2000), pp. 346–355.</ref>

<ref name="FMV">[[Uriel Feige|U. Feige]], V. Mirrokni and J. Vondr&aacute;k, Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), pp. 461–471.</ref>

<ref name="NVF"> [[George Nemhauser|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>

<ref name="CCPV"> G. Calinescu, C. Chekuri, M. P&aacute;l and J. Vondr&aacute;k, Maximizing a submodular set function subject to a matroid constraint, SIAM J. Comp. 40:6 (2011), 1740-1766.</ref>

<ref name="BFNS"> N. Buchbinder, M. Feldman, J. Naor and R. Schwartz, A tight linear time (1/2)-approximation for unconstrained submodular maximization, Proc. of 53rd FOCS (2012), pp. 649-658.</ref>

<ref name="FW"> Y. Filmus, J. Ward, A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, Proc. of 53rd FOCS (2012), pp. 659-668.</ref>

}}

Line 80 ⟶ 82:

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

*{{citation | last=Oxley | first=James G. | title=Matroid theory | series=Oxford Science Publications | ___location=Oxford | publisher=[[Oxford University Press]] | year=1992 | isbn=0-19-853563-5 | zbl=0784.05002 }}

<!--- Categories --->

[[Category:Combinatorial optimization| ]]

[[Category:Approximation algorithms| ]]