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
Dejar ser un conjunto yser una función establecida , dondedenota el conjunto de poder de. La función f es subaditiva si para cada subconjunto y de , tenemos . [1] [2]
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. Dejar tal que . Definircomo el número mínimo de subconjuntos necesarios para cubrir un conjunto dado. Formalmente, es el número mínimo tal que hay conjuntos satisfactorio . Luego es subaditivo.
El máximo de funciones de conjunto aditivo es subaditivo (doblemente, el mínimo de funciones aditivas es superaditivo ). Formalmente, para cada, dejar Ser funciones de conjunto aditivo. Luego es una función de conjunto subaditivo.
Las funciones de conjuntos fraccionalmente subaditivos son una generalización de funciones submodulares y un caso especial de funciones subaditivas. Una función subaditivaes además fraccionalmente subaditivo si satisface la siguiente definición. [1] Por cada, cada , y cada , Si , luego . 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. [1]
Ver también
Citas
- ↑ a b c Feige, Uriel (2009). "Sobre la maximización del bienestar cuando las funciones de utilidad son subditivas". Revista SIAM de Computación . 39 (1): 122-142. doi : 10.1137 / 070680977 .
- ^ Dobzinski, Shahar; Nisan, Noam ; Schapira, Michael (2010). "Algoritmos de aproximación para subastas combinatorias con licitadores sin complemento". Matemáticas de la investigación operativa . 35 (1): 1–13. doi : 10.1145 / 1060590.1060681 . S2CID 2685385 .