Moving Chen's lemma

1 files changed, 3 insertions, 11 deletions

diff --git a/main.tex b/main.tex
index 981eb05..fa8558e 100644
--- a/main.tex
+++ b/main.tex
@@ -17,21 +17,13 @@ element $i$ to be included is the one which maximizes the
 \end{align}
 This is repeated until the sum of costs of elements in $S$ reaches the budget
 constraint $B$. Denote by $S_G$ the set constructed by this heuristic and let
-$i^*$ be the element of maximum value. Then, the following lemma holds:
-\begin{lemma}~\cite{chen}\label{lemma:greedy-bound}
-Let $S_G$ be the set computed by the greedy algorithm and let 
-$i^* = \argmax_{i\in\mathcal{N}} V(\{i\}).$ We have:
-\begin{displaymath}
-OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
-\end{displaymath}
-\end{lemma}
-
-This lemma immediately implies that the following algorithm:
+$i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$ be the element of maximum value. Then,
+the following algorithm:
 \begin{equation}\label{eq:max-algorithm}
 \textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\}
 \;\textbf{else return}\; S_G
 \end{equation}
-has an approximation ratio of $\frac{5e}{e-1}$.
+has an approximation ratio of $\frac{5e}{e-1}$ \cite{chen}.
 
 \subsection{Submodular Maximization in the Strategic Case}