В математике субаддитивная функция множества - это функция множества , значение которой неформально имеет свойство, заключающееся в том, что значение функции на объединении двух множеств является не более чем суммой значений функции на каждом из множеств. Это тематически связано со свойством субаддитивности вещественных функций.
Определение
Позволять быть набором и- заданная функция , гдеобозначает набор мощности из. Функция F является субаддитивным , если для каждого подмножества а также из , у нас есть . [1] [2]
Примеры субаддитивных функций
Каждая неотрицательная субмодульная функция множества субаддитивна (семейство неотрицательных субмодульных функций строго содержится в семействе субаддитивных функций).
Функция, которая подсчитывает количество наборов, необходимых для покрытия данного набора, является субаддитивной. Позволять такой, что . Определятькак минимальное количество подмножеств, необходимое для покрытия данного набора. Формально, это минимальное количество такие, что есть наборы удовлетворение . потом является субаддитивным.
Максимум из аддитивных функций множества субаддитивен (дуально, то минимальный аддитивных функций сверхаддитивны ). Формально для каждого, позволять быть аддитивными функциями множества. потом является функцией субаддитивного набора.
Дробно субаддитивные функции множества являются обобщением субмодульных функций и частным случаем субаддитивных функций. Субаддитивная функциякроме того, является дробно субаддитивным, если он удовлетворяет следующему определению. [1] За каждые, каждый , и каждый , если , тогда . Набор дробно субаддитивных функций равен набору функций, которые можно выразить как максимум аддитивных функций, как в примере в предыдущем абзаце. [1]
Смотрите также
Цитаты
- ^ a b c Файги, Уриэль (2009). «О максимизации благосостояния при субаддитивных функциях полезности». SIAM Journal on Computing . 39 (1): 122–142. DOI : 10.1137 / 070680977 .
- ^ Добзинский, Шахар; Нисан, Ноам ; Шапира, Майкл (2010). «Алгоритмы приближения для комбинаторных аукционов с участниками торгов без дополнений». Математика исследования операций . 35 (1): 1–13. DOI : 10.1145 / 1060590.1060681 . S2CID 2685385 .