Add proof of lemma 4

1 files changed, 36 insertions, 2 deletions

diff --git a/proof.tex b/proof.tex
index 843b18b..de8eb82 100644
--- a/proof.tex
+++ b/proof.tex
@@ -127,7 +127,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \end{multline*}
 \end{proof}
 
-\begin{lemma}[Rounding]
+\begin{lemma}[Rounding]\label{lemma:rounding}
     For any feasible $\lambda\in[0,1]^n$, there exists a feasible
     $\bar{\lambda}\in[0,1]^n$ such that at most one of its component is
     fractional, that is, lies in $(0,1)$ and:
@@ -182,7 +182,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     $\lambda_\varepsilon$ becomes integral.
 \end{proof}
 
-\begin{lemma}
+\begin{lemma}\label{lemma:relaxation-ratio}
     The following inequality holds:
     \begin{displaymath}
         \forall\lambda\in[0,1]^n,\; 
@@ -330,6 +330,40 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \end{displaymath}
 \end{lemma}
 
+\begin{proof}
+    Let us consider a feasible point $\lambda^*\in[0,1]^n$ such that $L_\mathcal{N}(\lambda^*)
+    = OPT(L_\mathcal{N}, B)$. By applying lemma~\ref{lemma:relaxation-ratio}
+    and lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most
+    one fractional component such that:
+    \begin{equation}\label{eq:e1}
+        L_\mathcal{N}(\lambda^*) \leq \frac{1}{C_\kappa}
+        F_\mathcal{N}(\bar{\lambda})
+    \end{equation}
+
+    Let $\lambda_i$ denote the fractional component of $\bar{\lambda}$ and $S$
+    denote the set whose indicator vector is $\bar{\lambda} - \lambda_i e_i$.
+    Using the fact that $F_\mathcal{N}$ is linear with respect to the $i$-th
+    component and is a relaxation of the value function, we get:
+    \begin{displaymath}
+        F_\mathcal{N}(\bar{\lambda}) = V(S) +\lambda_i V(S\cup\{i\})
+    \end{displaymath}
+
+    Using the submodularity of $V$:
+    \begin{displaymath}
+        F_\mathcal{N}(\bar{\lambda}) \leq 2 V(S) + V(i)
+    \end{displaymath}
+
+    Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and
+    $V(S)\leq OPT(V,\mathcal{N}, B)$. Hence:
+    \begin{equation}\label{eq:e2}
+        F_\mathcal{N}(\bar{\lambda}) \leq 2 OPT(V,\mathcal{N}, B)
+        + \max_{i\in\mathcal{N}} V(i)
+    \end{equation}
+
+    Putting \eqref{eq:e1} and \eqref{eq:e2} together gives the results.
+
+\end{proof}
+
 \begin{algorithm}
     \caption{Budget feasible mechanism for ridge regression}
     \begin{algorithmic}[1]