The Art Gallery Guardian

Minimum of submodular function over family of subsets


Theorem1

Let LL and LL' are two lattices. If f:LRf:L \to \R is a submodular function and P:L2LP:L'\to 2^{L} is a function with the property that if XP(A)X\in P(A) and YP(B)Y\in P(B), then XYP(AB)X\wedge Y\in P(A\wedge B) and XYP(AB)X\vee Y\in P(A\vee B). fP:LRf_P:L'\to \R defined as fP(X)=minYP(X)f(Y)\displaystyle f_P(X) = \min_{Y\in P(X)} f(Y)\\ is submodular.

Proof

Let X=arg minYP(X)f(Y)X^* = \argmin_{Y\in P(X)} f(Y), note since XP(X)X^*\in P(X) and YP(Y)Y^*\in P(Y), we have XYP(XY)X^*\vee Y^* \in P(X\vee Y) and XYP(XY)X^*\vee Y^* \in P(X\wedge Y). fP(X)+fP(Y)=f(X)+f(Y)f(XY)+f(XY)f((XY))+f((XY))=fP(XY)+fP(XY)\displaystyle \begin{aligned} f_P(X) + f_P(Y) &= f(X^*) + f(Y^*)\\ &\geq f(X^* \vee Y^*) + f(X^*\wedge Y^*)\\ &\geq f((X\vee Y)^*) + f((X\wedge Y)^*)\\ &= f_P(X\vee Y) + f_P(X\wedge Y) \end{aligned}

This is quite useful, for starters, it proves that we can create a monotone submodular function from any submodular function.

Theorem2

Let f:2VRf:2^V\to \R be a submodular function, then f,f:2VRf_*,f^*:2^V\to \R defined as f(X)=min{f(Y)YX}f(X)=min{f(Y)XY}\displaystyle f_*(X) = \min \{f(Y)|Y\subset X\}\\ f^*(X) = \min \{f(Y)|X\subset Y\} are monotone and submodular.

A practical application is to generalize the cut function. Consider for a directed graph graph G=(V,E)G=(V,E). We would define δ+(A)\delta^+(A) to be the set of out going edges from AA to VAV\setminus A. f=δ+f=|\delta^+| is a submodular function. An alternate definition for ff is the minimum number of edges to be removed so there is no path from AA to VAV\setminus A.

A simple generalization is when we only care about TVT\subset V. We can define fT(A)f_T(A) to be the minimum number of edges to be removed so there is no path from AA to TAT\setminus A. Amazingly(or not not surprisingly, depending on your intuition), fTf_T is also a submodular function by invoking the next theorem, which is a direct corollary of our first theorem.

Theorem3

Let f:2VRf:2^V\to \R be a submodular function, then fT:2TRf_T:2^T\to \R defined as fT(X)=min{f(Y)YX,TXVY}\displaystyle f_T(X) = \min \{f(Y)|Y\subset X, T\setminus X\subset V\setminus Y\}\\ is submodular.

Posted by Chao Xu on .
Tags: submodular.