Submodular set function: Difference between revisions

Revision as of 18:49, 10 March 2023

Revision as of 10:47, 20 July 2023

Line 41:

=== Definition ===

A set-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, 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.

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