Función de conjunto subaditivo

En matemáticas, una función de conjunto subaditiva 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 funciones de valores reales.

Definición

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

Ejemplo cotidiano de subaditividad sigma: cuando se mezcla arena con agua, el volumen total de la mezcla es menor que la suma de los volúmenes individuales, ya que el agua puede alojarse en los espacios entre los granos de arena. Una situación similar con un mecanismo diferente ocurre cuando se mezcla etanol con agua, ver propiedad molar aparente .

Cada función de conjunto submodular no negativo 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 determinado es subaditiva. Deja tal que . Definir como el número mínimo de subconjuntos necesarios para cubrir un conjunto determinado. Formalmente, es el número mínimo tal que existen conjuntos que satisfacen . 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 (dualmente, 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}\colon \Omega \to \mathbb {R} _{+}}$ ${\displaystyle f(S)=\max _{i}\left(\sum _{x\in S}a_{i}(x)\right)}$

Las funciones de conjuntos fraccionalmente subaditivos son una generalización de funciones submodulares y un caso especial de funciones subaditivas. Además, una función subaditiva es fraccionariamente subaditiva si satisface la siguiente definición. ^[1] Para cada , cada y cada , si , entonces . El conjunto de funciones fraccionariamente subaditivas 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. ^[1] ${\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

1. Feige, Uriel (2009). "Sobre la maximización del bienestar cuando las funciones de utilidad son subaditivas". Revista SIAM de Computación . 39 (1): 122-142. doi : 10.1137/070680977.
2. Dobzinski, Shahar; Nisán, Noam ; Schapira, Michael (2010). "Algoritmos de aproximación para subastas combinatorias con postores sin complemento". Matemáticas de la Investigación de Operaciones . 35 (1): 1–13. CiteSeerX 10.1.1.79.6803 . doi :10.1145/1060590.1060681. S2CID  2685385.