Subaddytywna funkcja zbioru

W matematyce subaddytywna funkcja zbioru to funkcja zbioru , której wartość, nieformalnie, ma tę właściwość, że wartość funkcji na sumie dwóch zbiorów jest co najwyżej sumą wartości funkcji na każdym ze zbiorów. Jest to tematycznie związane z subaddytywności funkcji o wartościach rzeczywistych.

Definicja

Niech ${\ Displaystyle \ Omega}$ będzie zbiorem i będzie $}$ funkcji , gdzie fa $mathbb {R$ oznacza zestaw mocy Ω $\ Displaystyle \ Omega}$ . Funkcja f jest subaddytywna $,$ jeśli dla każdego i ${\ Displaystyle T}$ z ${\ Displaystyle \ Omega}$ , mamy ${\ Displaystyle f (S) + f (T) \ geq f (S \ kubek T)}$ .

Przykłady funkcji subaddytywnych

Każda nieujemna submodularna funkcja zbioru jest subaddytywna (rodzina nieujemnych funkcji submodularnych jest ściśle zawarta w rodzinie funkcji subaddytywnych).

Funkcja, która zlicza liczbę zestawów wymaganych do pokrycia danego zestawu, jest subaddytywna. Niech ${\ Displaystyle T_ {1}, \ kropka, T_ {m} \ subseteq \ Omega}$ takie, że ${\ Displaystyle \ kubek _ {i = 1}^{m}T_{i}=\Omega}$ . Zdefiniuj $liczbę$ podzbiorów wymaganych do pokrycia danego zestawu. Formalnie ${\ Displaystyle f (S)}$ $Displaystyle$ minimalna liczba taka, że istnieją zbiory $T_ {i_ {1}}, \ kropka, T_ {i_ {t}}}$ satysfakcjonujące ${\ Displaystyle S \ subseteq \ kubek _ {j = 1} ^ {t} T_ {i_ {j}}}$ . Wtedy $jest$ .

Maksimum funkcji zestawu addytywnego jest subaddytywne (podwójnie, minimum funkcji addytywnych jest superaddytywne ) . Formalnie dla każdego ${$ : $\ dwukropek$ będą addytywnymi funkcjami zbioru. Wtedy $\ Displaystyle f (S) = \ max _ {i} \ lewo (\ suma _ {x \ w S} a_ {i} (x) \ prawej)}$ jest subaddytywną funkcją zbioru.

Ułamkowo subaddytywne funkcje zbioru są uogólnieniem funkcji submodularnych i szczególnym przypadkiem funkcji subaddytywnych. Funkcja subaddytywna $,$ jeśli spełnia następującą definicję. Dla każdego, każdego $Displaystyle X_ {1}, \ kropka, X_ {n} \ subseteq \ Omega}$ $\$ α ${\ Displaystyle \ alfa _ {1}, \ kropka, \ alfa _ {n} \ w [0,1]}$ , jeśli ${\ styl wyświetlania 1_{S}\leq \sum _{i=1}^{n}\alpha _{i}1_{X_{i}}} ,$ wtedy ${\ Displaystyle f (S) \ równoważnik \ suma _ {i = 1} ^ {n} \ alfa _ {i} f (X_ {i})}$ . Zbiór funkcji ułamkowo subaddytywnych jest równy zbiorowi funkcji, które można wyrazić jako maksimum funkcji addytywnych, jak w przykładzie w poprzednim akapicie.

Zobacz też

Cytaty