Submodular set function: Difference between revisions

Revision as of 16:03, 25 October 2020

Revision as of 22:27, 26 November 2020

Line 21:

; Budget-additive functions : Any function of the form <math>f(S)=\min\left\{B,~\sum_{i\in S}w_i\right\}</math> for each <math>w_i\geq 0</math> and <math>B\geq 0</math> is called budget additive.{{citation needed|date=August 2014}}

; Coverage functions : Let <math>\Omega=\{E_1,E_2,\ldots,E_n\}</math> be a collection of subsets of some [[matroid|ground set]] <math>\Omega'</math>. The function <math>f(S)=\left|\bigcup_{E_i\in S}E_i\right|</math> for <math>S\subseteq \Omega</math> is called a coverage function. This can be generalized by adding non-negative weights to the elements.

; [[Entropy (information theory)|Entropy]] : Let <math>\Omega=\{X_1,X_2,\ldots,X_n\}</math> be a set of [[random variables]]. Then for any <math>S\subseteq \Omega</math> we have that <math>H(S)</math> is a submodular function, where <math>H(S)</math> is the entropy of the set of random variables <math>S</math>, a fact known as [[Entropic_vector#Shannon-type_inequalities_and_Γn|Shannon's inequality]].<ref>{{Cite web|url = https://www.cs.cmu.edu/~aarti/Class/10704_Spring15/lecs/lec3.pdf|title = Information Processing and Learning|date = |access-date = |website = |publisher = cmu|last = |first = }}</ref> Further inequalities for the entropy function are known to hold, see [[entropic vector]].

; [[Matroid]] [[matroid rank|rank functions]] : 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.<ref name=F22>Fujishige (2005) p.22</ref>

Line 64:

=== Submodular set function maximization===

Unlike the case of minimization, maximizing a submodular functions is [[NP-hard]] even in the unconstrained setting. For instance [[max cut]] is a special case even when the function is required only to be non-negative. The unconstrained problem can be shown to be inapproximable if it is allowed to be negative. There has been extensive work on constrained submodular function maximization when the functions are non-negative. Typically, the approximation algorithms for these problems are based on either [[greedy algorithm]]s or [[local search (optimization)|local search algorithm]]s. The problem of maximizing a non-negative symmetric submodular function admits a 1/2 approximation algorithm.<ref name="FMV" /> Computing the [[maximum cut]] of a graph is a special case of this problem. The more general problem of maximizing a non-negative submodular function also admits a 1/2 approximation algorithm.<ref name="BFNS" /> The problem of maximizing a monotone submodular function subject to a cardinality constraint admits a <math>1 - 1/e</math> approximation algorithm.<ref name="NVF" />{{page needed|date=October 2020}}<ref>{{Cite web|last=Williamson|first=David P.|date=|title=Bridging Continuous and Discrete Optimization: Lecture 23|url=https://people.orie.cornell.edu/dpw/orie6334/lecture23.pdf|url-status=live|archive-url=|archive-date=|access-date=|website=}}</ref> The [[maximum coverage problem]] is a special case of this problem. The more general problem of maximizing a monotone submodular function subject to a [[matroid]] constraint also admits a <math>1 - 1/e</math> approximation algorithm.<ref name="CCPV" /><ref name="FNS" /><ref name="FW" /> Many of these algorithms can be unified within a semi-differential based framework of algorithms.<ref name="IJB" />

===Related optimization problems===

Line 80:

{{reflist|30em|

refs=

<ref name="GLS">{{cite journal |authorlinkauthor-link=Martin Grötschel |first1=M. |last1=Grötschel |authorlink2author-link2=László Lovász |first2=L. |last2=Lovasz |authorlink3author-link3=Alexander Schrijver |first3=A. |last3=Schrijver |title=The ellipsoid method and its consequences in combinatorial optimization |journal=Combinatorica |volume=1 |issue=2 |year=1981 |pages=169–197 |doi=10.1007/BF02579273 |hdl=10068/182482 |s2cid=43787103 |hdl-access=free }}</ref>

<ref name="Cunningham">{{cite journal |first=W. H. |last=Cunningham |title=On submodular function minimization |journal=Combinatorica |volume=5 |issue=3 |year=1985 |pages=185–192 |doi=10.1007/BF02579361 |s2cid=33192360 }}</ref>

<ref name="IFF">{{cite journal |first1=S. |last1=Iwata |first2=L. |last2=Fleischer |first3=S. |last3=Fujishige |title=A combinatorial strongly polynomial algorithm for minimizing submodular functions |journal=J. ACM |volume=48 |year=2001 |issue=4 |pages=761–777 |doi=10.1145/502090.502096 |s2cid=888513 }}</ref>

<ref name="Schrijver">{{cite journal |authorlinkauthor-link=Alexander Schrijver |first=A. |last=Schrijver |title=A combinatorial algorithm minimizing submodular functions in strongly polynomial time |journal=J. Combin. Theory Ser. B |volume=80 |year=2000 |issue=2 |pages=346–355 |doi=10.1006/jctb.2000.1989 |url=https://ir.cwi.nl/pub/2108 }}</ref>

<ref name="IJB">R. Iyer, S. Jegelka and J. Bilmes, Fast Semidifferential based submodular function optimization, Proc. ICML (2013).</ref>

<ref name="IB">R. Iyer and J. Bilmes, Submodular Optimization Subject to Submodular Cover and Submodular Knapsack Constraints, In Advances of NIPS (2013).</ref>

Line 106:

== References ==

*{{Citation|last=Schrijver|first=Alexander|authorlinkauthor-link=Alexander Schrijver|year=2003|title=Combinatorial Optimization|___location=|publisher=[[Springer Publishing|Springer]]|isbn=3-540-44389-4}}

*{{Citation|last=Lee|first=Jon|authorlinkauthor-link=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}}

*{{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 }}