Функция субаддитивного набора - Subadditive set function

В математике функция субаддитивного набора это установить функцию чье значение неформально имеет свойство, заключающееся в том, что значение функции на объединении двух наборов является не более чем суммой значений функции на каждом из наборов. Это тематически связано с субаддитивность свойство вещественных функций.

Определение

Позволять ${\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)}$.^[1][2]

Примеры субаддитивных функций

Каждый неотрицательный функция субмодульного набора субаддитивен (семейство неотрицательных субмодулярных функций строго содержится в семействе субаддитивных функций).

Функция, подсчитывающая количество наборов, необходимых для крышка данный набор субаддитивен. Позволять ${\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}$ является субаддитивным.

В максимум из аддитивные функции множества является субаддитивным (вдвойне минимум аддитивных функций супераддитив ). Формально для каждого ${\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)}$ является функцией субаддитивного набора.

Дробно субаддитивные функции множества являются обобщением субмодульных функций и частным случаем субаддитивных функций. Субаддитивная функция ${\displaystyle f}$ кроме того, является дробно субаддитивным, если он удовлетворяет следующему определению.^[1] Для каждого ${\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})}$. Набор дробно субаддитивных функций равен набору функций, которые можно выразить как максимум аддитивных функций, как в примере в предыдущем абзаце.^[1]

Смотрите также

• Функция субмодульного набора
• Полезные функции для неделимых товаров

Цитаты

1. Файги, Уриэль (2009). «О максимизации благосостояния при субаддитивных функциях полезности». SIAM Журнал по вычислениям. 39 (1): 122–142. Дои:10.1137/070680977.
2. Добзинский, Шахар; Нисан, Ноам; Шапира, Майкл (2010). «Алгоритмы приближения для комбинаторных аукционов с участниками торгов без дополнений». Математика исследования операций. 35 (1): 1–13. Дои:10.1145/1060590.1060681. S2CID  2685385.