Underadditiv uppsättningsfunktion - Subadditive set function

I matematik är en subadditiv uppsättningsfunktion en uppsättningsfunktion vars värde, informellt, har egenskapen att funktionens värde vid sammansättningen av två uppsättningar högst är summan av funktionens värden på var och en av uppsättningarna. Detta är tematiskt relaterat till underadditivitetsegenskapen för verkligt värderade funktioner.

Definition

Låt vara en uppsättning och vara en uppsättningsfunktion , där betecknar kraftuppsättningen av . Funktionen f är underadditiv om vi har för varje delmängd och av . ${\ displaystyle \ Omega}$${\ displaystyle f \ colon 2 ^ {\ Omega} \ rightarrow \ mathbb {R}}$${\ displaystyle 2 ^ {\ Omega}}$${\ displaystyle \ Omega}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle \ Omega}$${\ displaystyle f (S) + f (T) \ geq f (S \ cup T)}$

Exempel på subadditiva funktioner

Varje icke-negativ submodulär uppsättningsfunktion är subadditiv (familjen av icke-negativa submodulära funktioner ingår strikt i familjen subadditiva funktioner).

Funktionen som räknar antalet uppsättningar som krävs för att täcka en viss uppsättning är underadditiv. Låt sådana att . Definiera som det minsta antal delmängder som krävs för att täcka en viss uppsättning. Formellt är det minsta antalet så att det finns uppsättningar som är tillfredsställande . Då är subadditiv. ${\ displaystyle T_ {1}, \ dotsc, T_ {m} \ subseteq \ Omega}$${\ displaystyle \ cup _ {i = 1} ^ {m} T_ {i} = \ Omega}$${\ displaystyle f}$${\ displaystyle f (S)}$${\ displaystyle t}$${\ displaystyle T_ {i_ {1}}, \ dotsc, T_ {i_ {t}}}$${\ displaystyle S \ subseteq \ cup _ {j = 1} ^ {t} T_ {i_ {j}}}$${\ displaystyle f}$

Den maximala av additiva inställda funktioner är subadditiv (dually, den minsta är av additiva funktioner superadditiv ). Formellt, för varje , låt vara tillsatsuppsättningsfunktioner. Då är en underadditiv uppsättningsfunktion. ${\ displaystyle i \ in \ {1, \ dotsc, m \}}$${\ displaystyle a_ {i} \ colon \ Omega \ to \ mathbb {R} _ {+}}$${\ displaystyle f (S) = \ max _ {i} \ left (\ sum _ {x \ in S} a_ {i} (x) \ right)}$

Fraktionellt subadditiva uppsättningsfunktioner är en generalisering av submodulära funktioner och ett speciellt fall av subadditiva funktioner. En subadditiv funktion är dessutom fraktionellt subadditiv om den uppfyller följande definition. För varje , varje och varje , om , då . Uppsättningen med fraktionellt underadditiva funktioner är lika med den uppsättning funktioner som kan uttryckas som det maximala antalet additiva funktioner, som i exemplet i föregående stycke. ${\ displaystyle f}$${\ displaystyle S \ subseteq \ Omega}$${\ displaystyle X_ {1}, \ dotsc, X_ {n} \ subseteq \ Omega}$${\ displaystyle \ alpha _ {1}, \ dotsc, \ alpha _ {n} \ in [0,1]}$${\ displaystyle 1_ {S} \ leq \ sum _ {i = 1} ^ {n} \ alpha _ {i} 1_ {X_ {i}}}$${\ displaystyle f (S) \ leq \ sum _ {i = 1} ^ {n} \ alpha _ {i} f (X_ {i})}$

Se även

• Submodulär set-funktion
• Verktygsfunktioner på odelbara varor

Citat