標籤：

這個函數是submodular的么?

01-30

$f:2^V o mathbb{R}$ 為一個submodular function.
讓 $f_T:2^T o mathbb{R}$ , $Tsubset V$ , $f_T(S) = min{ f(U) | S subset U, Tackslash S subset Vackslash U}$ .
$f_T$ 是submodular function么?

讓 $C_T(X) = {Y|Xsubset Y, Tsetminus Xsubset Vsetminus Y}$ 和 $X^* = argmin {f(Y)|C_T(X)}$ .

可以得知 $Xsubset X^*$ , $Tsetminus Xsubset Vsetminus X^*$ .

然後就能得到 $Acup Bsubset A^*cup B^*$ , $Tsetminus (Acup B) subset Vsetminus (A^*cup B^*)$ , 所以 $A^*cup B^* in C_T(Acup B)$ .

類似的, $Acap B subset A^*cap B^*$ , $Tsetminus (Acap B) subset Vsetminus (A^*cap B^*)$ , 所以 $A^*cap B^* in C_T(Acap B)$ .

$egin{align*} f_T(A)+f_T(B) = f(A^*)+f(B^*)\ geq f(A^*cup B^*)+f(A^*cap B^*)\ geq f((Acup B)^*)+f((Acap B)^*)\ = f_T(Acup B)+f_T(Acap B) end{align*}$

抽象出來這個證明方法可以直接獲得更加強的定理...

$f:2^V o mathbb{R}$ 是一個submodular function, $P:2^T o 2^{2^V}$ 滿足以下屬性, 如果 $Xin P(A)$ , $Yin P(B)$

1. $Xcup Yin P(Acup B)$

2. $Xcap Yin P(Acap B)$

則 $f_P:2^T o mathbb{R}$ 定義為

$f_P(X) = min_{Yin P(X)} f(Y)$

也是submodular function.

這樣只要集合滿足了那個條件就直接指導是submodular的了.

推薦閱讀：

※C++返回類型為類類型的函數返回的臨時變數賦值及生存周期？
※求反函數清晰的定義。？
※是不是任意曲線都有其對應函數公式？

TAG:函數 |