Optimization for a sum of submodular functions

Question

I know $H(A), A\in E$, $F(B), B\in W, E\cap W = \varnothing$, and $K(C), C\in E\cup W$ are all submodular functions. I am wondering whether I can maximize $H(A)+F(B)+K(C)$ via the greedy method with the 1/2 approximation guarantee.

Answer 1

The answer is yes. We can define a new submodular function $\bar{H}(A)$, where $A\in E\cup W$, as following $\bar{H}(A) = \left\{\begin{matrix} H(A) & A\in E \\ H(X) & A\cap E = X, A\cap W = Y \\ 0 & A\in W \end{matrix}\right.$.

We can prove that $\bar{H}(A)$ is still a submodular function but its ground set has become $E\cup W$. We do a similar thing to $F$, then we have $\bar{F}(B)$, where $B\in E\cup W$. So the overall function become that, $\bar{H}(X)+\bar{F}(X) + K(X)$, where $X\in E\cup W$. It is also submodular and we can use the greedy algorithm to solve it.