Small fixes in main section up to the subsection 4.2

1 files changed, 11 insertions, 11 deletions

diff --git a/main.tex b/main.tex
index 8c57916..64d4604 100644
--- a/main.tex
+++ b/main.tex
@@ -138,10 +138,10 @@ set can be found in~\cite{singer-mechanisms}.
     \begin{algorithmic}[1]
     \State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$
     \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
-    \State $\xi \gets \argmax_{\lambda\in[0,1]^{n}} \{L(\lambda)
+    \State $L^* \gets \argmax_{\lambda\in[0,1]^{n}} \{L(\lambda)
                                     \mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$
         \Statex
-        \If{$L(\xi) < C \cdot V(i^*)$} \label{c}
+        \If{$L^* < C \cdot V(i^*)$} \label{c}
             \State \textbf{return} $\{i^*\}$ 
         \Else
             \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
@@ -227,18 +227,18 @@ in the above formula:
     \lambda_i x_i\T{x_i}\right)
 \end{align}
 \end{comment}
+
 \subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
 %\stratis{individual rationality???}
 %The proof of the properties of the mechanism is broken down into lemmas.
 
 We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual
 rationality follows from monotonicity and threshold payments.  Monotonicity and
-budget feasibility follow the same steps as the analysis of Chen \emph{et al.} \cite{chen};
+budget feasibility follow the same steps as the analysis of \citeN{chen};
  for the sake of completeness, we restate their proof in the Appendix.
- Our proof of the approximation ratio uses a bound on our concave relaxation
-$L$ (Lemma~\ref{lemma:relaxation}). This is our main technical
-contribution; the proof of this lemma can be found in Section~\ref{sec:relaxation}.
-\begin{lemma}\label{lemma:complexity}
+
+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}
@@ -264,7 +264,7 @@ contribution; the proof of this lemma can be found in Section~\ref{sec:relaxatio
 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$.  
-\begin{lemma}\label{lemma:relaxation}
+\begin{lemma}[Approximation]\label{lemma:relaxation}
     %\begin{displaymath}
      $   OPT' \leq 2 OPT
         + 2\max_{i\in\mathcal{N}}V(i)$
@@ -317,11 +317,11 @@ Using Lemma~\ref{lemma:relaxation} we can complete the proof of Theorem~\ref{thm
         + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}
     \end{align*}
     Finally, using again Lemma~\ref{lemma:greedy-bound}, we get:
-    \begin{multline}\label{eq:bound2}
+    \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)\\
+        (e-1) -6e  +2}\right) V(S_G)
         +\frac{2e\varepsilon}{C(e-1)- 6e + 2}
-    \end{multline}
+    \end{equation}
     To minimize the coefficients of $V_{i^*}$  and $V(S_G)$  in \eqref{eq:bound1} and \eqref{eq:bound2} respectively,
     we wish to chose for $C=C^*$ such that:
     \begin{displaymath}