Moving Chen's lemma

1 files changed, 17 insertions, 3 deletions

diff --git a/proofs.tex b/proofs.tex
index 28f13ac..9358a3d 100644
--- a/proofs.tex
+++ b/proofs.tex
@@ -32,13 +32,27 @@ The complexity of the mechanism is given by the following lemma.
 \end{proof}
 
 Finally, we prove the approximation ratio of the mechanism. We use the
-following lemma  which establishes that $OPT'$, the optimal value \eqref{relax} of the fractional relaxation $L$ under the budget constraints
- is not too far from $OPT$.  
+following lemma  which establishes that $OPT'$, the optimal value \eqref{relax}
+of the fractional relaxation $L$ under the budget constraints is not too far
+from $OPT$.  
 \begin{lemma}[Approximation]\label{lemma:relaxation}
      $   OPT' \leq 2 OPT
         + 2\max_{i\in\mathcal{N}}V(i)$.
 \end{lemma}
-The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}.
+The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution,
+and can be found in Section \ref{sec:relaxation}.
+
+We also use the following lemma from \cite{chen} which bounds $OPT$ in terms of
+the value of $S_G$, as computed in Algorithm \ref{mechanism}, and $i^*$, the
+element of maximum value.
+
+\begin{lemma}[\cite{chen}]
+Let $S_G$ be the set computed in Algorithm \ref{mechanism} 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}
 
 Using Lemma~\ref{lemma:relaxation} we can complete the proof of
 Theorem~\ref{thm:main} by showing that, for any $\varepsilon > 0$, if