From 3e867d20578387a3847259c042a229fb365189e4 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 4 Nov 2012 15:39:28 -0800
Subject: l8

---
 main.tex | 12 ++++--------
 1 file changed, 4 insertions(+), 8 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 9d840da..a91e67e 100644
--- a/main.tex
+++ b/main.tex
@@ -289,25 +289,21 @@ Its proof is our main technical contribution, and can be found in Section \ref{s
     Let $x^*\in [0,1]^{n-1}$ be the true maximizer of $L_{\mathcal{N}\setminus\{i^*\}}$ subject to the budget constraints. Assume that on line 2 of algorithm~\ref{mechanism}, a quantity
     $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq L_{\mathcal{N}\setminus {i^*}}(x^*) \leq
     \tilde{L}+\varepsilon$ has been computed (lemma~\ref{lemma:complexity}
-    states that this can be done in a time within our complexity guarantee).
-    
+    states that this  is computed in time within our complexity guarantee).
     If the condition on line 3 of the algorithm holds, then:
     \begin{displaymath}
         V(i^*) \geq \frac{1}{C}L(x^*)-\frac{\varepsilon}{C} \geq
-        \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B)
+        \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B) -\frac{\varepsilon}{C} 
     \end{displaymath}
-
-    But:
+    as $L$ is a fractional relaxation of $V$ on $\mathcal{N}\setminus \{i^*\}$. Also,
     \begin{displaymath}
         OPT(V,\mathcal{N},B) \leq OPT(V,\mathcal{N}\setminus\{i\}, B) + V(i^*)
     \end{displaymath}
-
     Hence:
     \begin{equation}\label{eq:bound1}
         OPT(V,\mathcal{N}, B)\leq (1+C)V(i^*) + \varepsilon
     \end{equation}
-
-    If the condition of the algorithm does not hold, by applying lemmas
+    If the condition of the algorithm does not hold, by applying Lemmas
     \ref{lemma:relaxation} and \ref{lemma:greedy-bound}:
     \begin{align*}
         V(i^*) & \leq \frac{1}{C}L(x^*) + \frac{\varepsilon}{C}\leq \frac{1}{C}
-- 
cgit v1.2.3-70-g09d2

