From 8f788bc40d01316c47713028c2e4cce94b65de49 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 30 Oct 2012 19:45:00 +0100
Subject: Add a missing piece of the proof

---
 main.tex | 30 +++++++++++++++++++-----------
 1 file changed, 19 insertions(+), 11 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 44851c1..b089dcc 100644
--- a/main.tex
+++ b/main.tex
@@ -18,11 +18,12 @@ Unfortunately, even for the non-strategic case, the greedy heuristic gives an
 unbounded approximation ratio. It has been noted by Khuller et al.
 \cite{khuller} that for the maximum coverage problem, taking the maximum
 between the greedy solution and the point of maximum value gives
-a $\frac{2e}{e-1}$ approximation ration. In the general case, lemma 3.1 from
+a $\frac{2e}{e-1}$ approximation ratio. In the general case, lemma 3.1 from
 \cite{singer-influence} which follows from \cite{chen}, shows that this has an
-approximation ratio of $\frac{5e}{e-1}$. However, Singer
-\cite{singer-influence} notes that this approach breaks incentive compatibility
-and therefore cannot be directly applied to the strategic case.
+approximation ratio of $\frac{5e}{e-1}$ (see lemma~\ref{lemma:greedy-bound}
+below). However, Singer \cite{singer-influence} notes that this approach breaks
+incentive compatibility and therefore cannot be directly applied to the
+strategic case.
 
 Two approaches have been studied to deal with the strategic case and rely on
 comparing the point of maximum value to a quantity which can be proven to be
@@ -168,7 +169,18 @@ readibility, the proof is postponed to section~\ref{sec:relaxation}.
     \end{displaymath}
 \end{lemma}
 
-\begin{lemma}
+Let us recall here the following lemma from \cite{chen} which we use in the
+proof of lemma~\ref{lemma:approx}. This lemma shows, as mentioned above, that
+taking the maximum between the greedy solution and the point of maximum value
+gives a $\frac{5e}{e-1}$ approximation ratio.
+\begin{lemma}\label{lemma:greedy-bound}
+The following inequality holds:
+\begin{displaymath}
+    OPT(V,\mathcal{N},B) \leq \frac{5e}{e-1}\max\big( V(S_M), V(i^*)\big)
+\end{displaymath}
+\end{lemma}
+
+\begin{lemma}\label{lemma:approx}
     Let us denote by $S_M$ the set returned by the mechanism. Let us also
     write:
     \begin{displaymath}
@@ -183,6 +195,7 @@ readibility, the proof is postponed to section~\ref{sec:relaxation}.
     \end{displaymath}
 \end{lemma}
 
+
 \begin{proof}
 
     If the condition on line 3 of the algorithm holds, then:
@@ -215,12 +228,7 @@ readibility, the proof is postponed to section~\ref{sec:relaxation}.
         V(i^*) \leq \frac{6e}{C\cdot C_\mu(e-1)- 5e + 1} V(S_M)
     \end{align*}
 
-    Finally, using again that:
-    \begin{displaymath}
-        OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big(3 V(S_M) + 2 V(i^*)\big)
-    \end{displaymath}
-    
-    We get:
+    Finally, using again lemma~\ref{lemma:greedy-bound}, we get:
     \begin{displaymath}
         OPT(V, \mathcal{N}, B) \leq \frac{e}{e-1}\left( 3 + \frac{12e}{C\cdot
         C_\mu(e-1) -5e  +1}\right) V(S_M)
-- 
cgit v1.2.3-70-g09d2

