From c7b0c48affdf7bb19417a4016ba2a871792fbca6 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 11 Feb 2013 19:02:57 -0800
Subject: Moving Chen's lemma

---
 main.tex | 14 +++-----------
 1 file changed, 3 insertions(+), 11 deletions(-)

(limited to 'main.tex')

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}
 
-- 
cgit v1.2.3-70-g09d2