# Why is this greedy algorithm claim true?

I'm taking a course about submodular functions and their applications towards influence maximization in a network. We've been discussing a greedy algorithm for selecting $k$ initial nodes to maximize influence and I'm confused about a statement made in class.

Let $O = \{o_1, . . . , o_l\}$, and $o_{\max}$ be the element with the highest marginal contribution in $O$ at stage $i + 1$. That is: $o_{\max} = \arg\max_{o\in O} f_{S_i}(o)$. At stage $i + 1$ the algorithm selects element $a_i+1$ and we are guaranteed that its marginal contribution is the highest. In particular, its marginal contribution is also higher than the marginal contribution of the element in $O$ that has the highest marginal contribution: $$f_{S_i}(a_i+1) \geq f_{S_i}(o_{\max})$$

$f$ gives the expected number of nodes influenced and $f_S$ is the marginal contribution of adding set $a$ to set $S$ ie: $f_S(a) = f(S\cup a) - f(S)$ $$f_{S}(a) \geq f_S(o^*)\,.$$

This doesn't make sense to me. Consider the circle cover problem:

At timestep $t = 1$, the greedy algorithm selects $A$ and optimal selects $B$. (Greedy is on the left and optimal is on the right).

$$f_S(A) \geq f_S(B)\,,$$ but at $t=2$ the greedy selects $B$ and optimal selects $C$. $$f_S(B) \ngeqslant f_S(C)\,,$$ because the marginal contribution of the greedy algorithm is only 4 when the optimal is 5.

Why did we say that selecting elements greedily has better marginal contributions than optimal? I'd appreciate a theoretical and possible concrete example if possible!

The claim is not that

$$f_S(B) \ge f_S(C).$$

Rather, the claim is that

$$f_{S_1}(B) \ge f_{S_1}(C).$$

Do you see the difference? Here $S_i$ is the set of elements chosen (by the greedy algorithm) in the first $i$ iterations, so $S_i=\{A\}$. Thus, the claim is that

$$f_{\{A\}}(B) \ge f_{\{A\}}(C),$$

i.e.,

$$f(\{A\} \cup \{B\}) \ge f(\{A\} \cup \{C\}).$$

The latter claim is indeed true, as both the left-hand side and the right-hand side are 9 (i.e., $f(\{A,B\})=f(\{A,C\})=9$), since they cover 9 of the "blue dots".

• So I see that they are equivalent, but I cannot come up with a scenario where $f_S(a) > f_S(o)$ where a is from a greedy algorithm and o is from a optimal algorithm – William Gottschalk Mar 29 '17 at 3:36
• @WilliamGottschalk, You are right! Good observation. Indeed, that cannot happen (nothing can be better than optimal). So if you prefer, you can view the claim as saying that $f_S(a) = f_S(o)$. – D.W. Mar 29 '17 at 6:00