Some fixes to main and proof sections

1 files changed, 18 insertions, 11 deletions

diff --git a/proofs.tex b/proofs.tex
index ba22501..eb1226c 100644
--- a/proofs.tex
+++ b/proofs.tex
@@ -6,10 +6,12 @@ budget feasibility follow the same steps as the analysis of \citeN{chen};
  for the sake of completeness, we restate their proof in the Appendix.
 
 The complexity of the mechanism is given by the following lemma.
+
 \begin{lemma}[Complexity]\label{lemma:complexity}
     For any $\varepsilon > 0$, the complexity of the mechanism  is
     $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$.
 \end{lemma}
+
 \begin{proof}
     The value function $V$ in \eqref{modified} can be computed in time
     $O(\text{poly}(n, d))$ and the mechanism only involves a linear
@@ -50,11 +52,12 @@ OPT
 \end{equation}
 To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to
 $\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume
-that on line 3 of algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that
+that on line 3 of Algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that
 $\tilde{L}-\varepsilon\leq OPT_{-i^*}' \leq \tilde{L}+\varepsilon$ has been
 computed (Lemma~\ref{lemma:complexity} states that this  is computed in time
-within our complexity guarantee).  If the condition on line 3 of the algorithm
-holds, then:
+within our complexity guarantee).
+
+If the condition on line 3 of the algorithm holds, then:
 \begin{displaymath}
     V(i^*) \geq \frac{1}{C}OPT_{-i^*}'-\frac{\varepsilon}{C} \geq
     \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C} 
@@ -64,20 +67,24 @@ hence:
 \begin{equation}\label{eq:bound1}
     OPT\leq (1+C)V(i^*) + \varepsilon
 \end{equation}
-Note that $OPT_{-i^*}'\leq OPT'$. If the condition  does not hold, from Lemmas
-\ref{lemma:relaxation} and \ref{lemma:greedy-bound}:
-\begin{align*}
-    V(i^*) & \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C}
-    \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\
-    & \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G)
+
+If the condition  does not hold, by observing that $OPT'_{-i^*}\leq OPT'$ and
+applying Lemma~\ref{lemma:relaxation}, we get:
+\begin{displaymath}
+    V(i^*)  \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C}
+    \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}
+\end{displaymath}
+Applying Lemma~\ref{lemma:greedy-bound}:
+\begin{displaymath}
+    V(i^*) \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G)
     + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C}
-\end{align*}
+\end{displaymath}
 Thus, if $C$ is such that $C(e-1) -6e  +2 > 0$,
 \begin{align*}
     V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) 
     + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}
 \end{align*}
-Finally, using again Lemma~\ref{lemma:greedy-bound}, we get:
+Finally, using Lemma~\ref{lemma:greedy-bound} again, we get:
 \begin{equation}\label{eq:bound2}
     OPT(V, \mathcal{N}, B) \leq 
     \frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}\right) V(S_G)