Función de conjunto de subtipos - Subadditive set function

En matemáticas, una función de conjunto subaditivo es una función de conjunto cuyo valor, informalmente, tiene la propiedad de que el valor de la función en la unión de dos conjuntos es como máximo la suma de los valores de la función en cada uno de los conjuntos. Esto está relacionado temáticamente con la propiedad de subaditividad de las funciones de valor real.

Definición

Sea un conjunto y sea ​​una función de conjunto , donde denota el conjunto de potencia de . La función f es subaditiva si para cada subconjunto y de , tenemos . ${\ 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)}$

Ejemplos de funciones subaditivas

Cada función de conjunto submodular no negativa es subaditiva (la familia de funciones submodulares no negativas está estrictamente contenida en la familia de funciones subaditivas).

La función que cuenta el número de conjuntos necesarios para cubrir un conjunto dado es subaditiva. Que tal eso . Defina como el número mínimo de subconjuntos necesarios para cubrir un conjunto dado. Formalmente, es el número mínimo para que haya conjuntos satisfactorios . Entonces es subaditivo. ${\ 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}$

El máximo de funciones del conjunto aditivo es subaditivo (doblemente, el mínimo de funciones aditivas es superaditivo ). Formalmente, para cada uno , sean funciones de conjunto aditivo. Entonces es una función de conjunto subaditivo. ${\ Displaystyle i \ in \ {1, \ dotsc, m \}}$${\ Displaystyle a_ {i} \ dos puntos \ Omega \ a \ mathbb {R} _ {+}}$${\ Displaystyle f (S) = \ max _ {i} \ left (\ sum _ {x \ in S} a_ {i} (x) \ right)}$

Las funciones de conjuntos subaditivos fraccionales son una generalización de funciones submodulares y un caso especial de funciones subaditivas. Una función subaditiva es además fraccionalmente subaditiva si satisface la siguiente definición. Para todos , todos y cada uno , si , entonces . El conjunto de funciones subaditivas fraccionadas es igual al conjunto de funciones que se pueden expresar como el máximo de funciones aditivas, como en el ejemplo del párrafo anterior. ${\ 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})}$

Ver también

• Función de conjunto submodular
• Funciones de utilidad sobre bienes indivisibles

Citas