Submodular set function: Difference between revisions

Revision as of 18:57, 21 October 2022

Revision as of 19:33, 21 October 2022

Line 41:

=== Definition ===

ForA a submodularset-valued function <math>f:2^{\Omega}\rightarrow \mathbb{R}</math> with <math>|\Omega|=n</math> can also be represented as a function on <math>\{0, we1\}^{n}</math>, canby associateassociating each <math>S\subseteq \Omega</math> with a binary vector <math>x^{S}\in \{0, 1\}^{n}</math> such that <math>x_{i}^{S}=1</math> when <math>i\in S</math>, and <math>x_{i}^{S}=0</math> otherwise. In this sense, the submodular function can be seen as a function defined on <math>\{0, 1\}^{n}</math>. We can then define the

The ''continuous [[Restriction_(mathematics)#Extension_of_a_function|extension]]'' of <math>f</math> is defined to be any continuous function <math>F:\mathbb{R}[0, 1]^{n}\rightarrow \mathbb{R}</math> such that it matches the value of the submodular function<math>f</math> on <math>x\in \{0, 1\}^{n}</math>, i.e. <math>F(x^{S})=f(S)</math>. Some commonly used continuous extensions are as follows.

In the context of submodular functions, there are a few examples of continuous extensions that are commonly used, which are described as follows.

=== Examples ===

Line 52 ⟶ 56:

==== Convex closure ====

Consider any vector <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the convex closure is defined as <math>f^-(\mathbf{x})=\min\left(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\mathbf{x},\sum_S \alpha_S=1,\alpha_S\geq 0\right)</math>. The convex closure of any set function is convex over <math>[0,1]^n</math>. It can be shown that <math>f^L(\mathbf{x})=f^-(\mathbf{x})</math> for submodular functions.

==== Concave closure ====

Consider any vector <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the concave closure is defined as <math>f^+(\mathbf{x})=\max\left(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\mathbf{x},\sum_S \alpha_S=1,\alpha_S\geq 0\right)</math>.

=== Connections between extensions ===

For the extensions discussed above, it can be shown that <math>f^{+}(\mathbf{x}) \geq F(\mathbf{x}) \geq f^{-}(\mathbf{x})=f^L(\mathbf{x})</math> when <math>f</math> is submodular.<ref name="JV2" />

== Properties ==

Line 110 ⟶ 117:

<ref name="L">{{cite journal |author-link1=László Lovász |last1=Lovász |first1=L. |date=1983 |title=Submodular functions and convexity |url= |journal=Mathematical Programming The State of the Art |pages=235-257 |doi=10.1007/978-3-642-68874-4_10 }}</ref>

<ref name="BF">{{cite encyclopedia |last1=Buchbinder |first1=Niv |last2=Feldman |first2=Moran |title=Submodular Functions Maximization Problems |encyclopedia= Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications |year=2018 |editor1-last=Gonzalez |editor1-first=Teofilo F. |publisher=Chapman and Hall/CRC |doi=10.1201/9781351236423 |url=https://www.taylorfrancis.com/chapters/edit/10.1201/9781351236423-42/submodular-functions-maximization-problems-niv-buchbinder-moran-feldman}}</ref>

<ref name="JV2">{{Cite web|last=Vondrák|first=Jan|title=Polyhedral techniques in combinatorial optimization: Lecture 17|url=https://theory.stanford.edu/~jvondrak/CS369P/lec17.pdf}}</ref>

}}