Submodular set function: Difference between revisions

Revision as of 11:08, 31 August 2023

Revision as of 21:46, 25 September 2023

Line 38:

; Directed cuts : 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>. This can be generalized by adding non-negative weights to the directed edges.

== Continuous extensions of submodular set functions ==

Often, given a submodular set function that describes the values of various sets, we need to compute the values of ''fractional'' sets. For example: we know that the value of receiving house A and house B is V, and we want to know the value of receiving 40% of house A and 60% of house B. To this end, we need a ''continuous extension'' of the submodular set function.

AFormally, a set function <math>f:2^{\Omega}\rightarrow \mathbb{R}</math> with <math>|\Omega|=n</math> can also be represented as a function on <math>\{0, 1\}^{n}</math>, by associating 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. A ''continuous [[Restriction_(mathematics)#Extension_of_a_function|extension]]'' of <math>f</math> is a continuous function <math>F:[0, 1]^{n}\rightarrow \mathbb{R}</math>, that matches the value of <math>f</math> on <math>x\in \{0, 1\}^{n}</math>, i.e. <math>F(x^{S})=f(S)</math>.

=== Definition ===

A set function <math>f:2^{\Omega}\rightarrow \mathbb{R}</math> with <math>|\Omega|=n</math> can also be represented as a function on <math>\{0, 1\}^{n}</math>, by associating 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.

Several kinds of continuous extensions of submodular functions are commonly used, which are described below.

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

==== Lovász extension ====

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

=== Examples ===

==== Lovász extension ====

This extension is named after mathematician [[László Lovász]].<ref name="L" /> 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 Lovász extension is defined as <math>f^L(\mathbf{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 if and only if <math>f</math> is a submodular function.

==== Multilinear extension ====

Consider any vector <math>\mathbf{x}=\{x_1,x_2,\ldots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the multilinear extension is defined as <math>F(\mathbf{x})=\sum_{S\subseteq \Omega} f(S) \prod_{i\in S} x_i \prod_{i\notin S} (1-x_i)</math>.

Intuitively, ''x_i'' represents the probability that item ''i'' is chosen for the set. For every set ''S'', the two inner products represent the probability that the chosen set is exactly ''S''. Therefore, the sum represents the expected value of ''f'' for the set formed by choosing each item ''i'' at random with probability xi, independently of the other items.

==== Convex closure ====

==== 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>.

==== 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>.

=== ConnectionsRelations between continuous 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" />