1
$\begingroup$

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: enter image description here

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!

$\endgroup$
1
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – William Gottschalk Mar 29 '17 at 3:36
  • $\begingroup$ @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)$. $\endgroup$ – D.W. Mar 29 '17 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.