submodular 子模性質

若 $$ A \subseteq B \subseteq V ,e \in V - B $$, 則對于集合函數f()，如果：$$ f(A \bigcup { e }) - f(A) >= f(B \bigcup { e }) - f(B)$$ 成立，則說f()函數是子模的。

一句話概括就是增益遞減。比如如果Alice每日的早餐食譜如果隻有三明治和奶茶，後來添加了培根，他開心增量為x；如果Alice每日的早餐食譜已經有三明治、奶茶、熱狗、薯條、聖代，後來添加了培根，他的開心增量為y；顯然x > y。“通俗的說就是你把所有商品看成一個集合，随着你所擁有的物品數量的增加，那麼你獲得剩下物品所得到的滿足程度越來越小”。假設你已經有100萬資産，通過做生意又掙了100萬；再假設你已經有了一千萬，通過做生意掙了100萬；那麼顯然前者的收獲感強于後者。

例子如下：u = {1,2,3,4,5,6,7,8}，A = {1,2,3}，B = {1,2,3,5,6}，定義f(A) = |A| ，即集合A的元素個數。

是以：f(A+e) - f(A) >= f(B+e) - f(B)，例如e = {3,4,5}，因為 5 - 3 >= 6 - 5。

​