Una función de conjunto es monótono submodular si para todos , A , B f ( A ) + f ( B ) ≥ f ( A ∪ B ) + f ( A ∩ B ) .
Una propiedad más fuerte es Tomando , esta propiedad implica submodularidad monótona.C=A∪B
¿Se conoce esta propiedad?
Antecedentes
Esta propiedad surgió al intentar caracterizar las funciones de cobertura. Teniendo en cuenta algún universo ponderado (todos los pesos son no negativo) y una familia de subconjuntos de , la función de cobertura se define por como el peso total de los elementos cubiertos por conjuntos en . La función es siempre monótona y submodular. Lo contrario no es cierto.
La propiedad en cuestión implica que es una función de cobertura en el caso . Propiedades similares y más complicadas funcionan para más grande . Todas estas propiedades son satisfechas por las funciones de cobertura, por lo que esta es una caracterización completa.
fuente
fuente