small changes

1 files changed, 3 insertions, 4 deletions

diff --git a/paper/supplementary.tex b/paper/supplementary.tex
index 8839b7c..8c5b338 100644
--- a/paper/supplementary.tex
+++ b/paper/supplementary.tex
@@ -18,7 +18,7 @@
 
 \paragraph{Notation}
 
-Let $G = (V, E)$ be a weighted directed graph. Without loss of generality, we can assign a weight $p_{u,v} \in [0,1]$ to every possible edge $(u,v) \in V^2$. Let $m$ be the number of non-zero edges of $G$. Let $\sigma_G(S)$ be the influence of the set $S \subseteq V$ in graph $G$ under the independent cascade model. For $k \in \mathbb{N}^*$, let $O_k \in \arg\max_{|S| \leq k} \sigma_G(S)$ and $\sigma_{k,G}^* = \sigma_G(O_k)$
+Let $G = (V, E)$ be a weighted directed graph. Without loss of generality, we can assign a weight $p_{u,v} \in [0,1]$ to every possible edge $(u,v) \in V^2$. Let $m$ be the number of non-zero edges of $G$. Let $\sigma_G(S)$ be the influence of the set $S \subseteq V$ in graph $G$ under the independent cascade model. For $k \in \mathbb{N}^*$, let $O_k \in \arg\max_{|S| \leq k} \sigma_G(S)$ and $\sigma_{G}^* = \sigma_G(O_k)$ where we omit the $k$ when it is unambiguous.
 
 \begin{claim}
 \label{cla:oracle}
@@ -38,7 +38,7 @@ $$\frac{\sigma_{G'}(S)[v]}{\sigma_{G}(S)[v]} \geq \mathbb{E} \left[ \frac{\mathb
 It follows that $\sigma_{G'}(S)[v] \geq (1 -1/\alpha) \sigma_{G}(S)[v]$.
 \end{proof}
 
-Note that in the limit of large $m$, $(1 -\frac{1}{\alpha m})^m \rightarrow \exp(-1/\alpha)$ and the approximation ratio goes to $\exp(-1/\alpha)$. We can use Claim~\ref{cla:oracle} to find a constant factor approximation algorithm to maximising influence on $G$ by maximising influence on $G'$:
+ We can use Claim~\ref{cla:oracle} to find a constant factor approximation algorithm to maximising influence on $G$ by maximising influence on $G'$:
 
 \begin{proposition}
 \label{prop:approx_optim}
@@ -49,8 +49,7 @@ Suppose we have an unknown graph $G$ and a known graph $G'$ such that $V = V'$ a
 For every edge $(u,v) \in V^2$, let $\hat p = p'_{u,v} - \frac{1}{\alpha m}$. We are now in the conditions of Claim~\ref{cla:oracle} with $\alpha \leftarrow \alpha/2$. We return the set $\hat O_k$ obtained by greedy maximisation on $\hat G$. It is a classic exercise to show then that $\sigma_G(\hat O_k) \geq 1 - e^{\frac{2}{\alpha} - 1}$ (see Pset 1, CS284r).
 \end{proof}
 
-A small note on the approximation factor: it is only $>0$ for $\alpha > 2$. Note that $\alpha \geq 7 \implies 1 - e^{\frac{2}{\alpha} - 1} \geq \frac{1}{2}$ and that it converges to $(1 - 1/e)$
-
+A small note on the approximation factor: it is only $>0$ for $\alpha > 2$. Note that $\alpha \geq 7 \implies 1 - e^{\frac{2}{\alpha} - 1} \geq \frac{1}{2}$ and that it converges to $(1 - 1/e)$ which is the best possible polynomial-time approximation ratio to influence maximisation unless $P = NP$. Also note that in the limit of large $m$, $(1 -\frac{1}{\alpha m})^m \rightarrow \exp(-1/\alpha)$ and the approximation ratio goes to $1 - \exp(-\exp(-1/\alpha))$.
 
 \subsection*{Obtaining $\| p - p^*\|_{\infty} \leq 1/2m$}