Specify the optimal value for C and the approximation ration

1 files changed, 34 insertions, 4 deletions

diff --git a/proof.tex b/proof.tex
index 7b2088f..25061bd 100644
--- a/proof.tex
+++ b/proof.tex
@@ -364,7 +364,9 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     Putting \eqref{eq:e1} and \eqref{eq:e2} together gives the results.
 \end{proof}
 
-\begin{algorithm}
+\subsection{The mechanism}
+
+\begin{algorithm}\label{mechanism}
     \caption{Budget feasible mechanism for ridge regression}
     \begin{algorithmic}[1]
     \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
@@ -386,6 +388,10 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \end{algorithmic}
 \end{algorithm}
 
+The constant $C$ which appears in the mechanism is unspecified for now. We can
+make the analysis regardless of its value. The optimal value will be specified
+in the theorem.
+
 \begin{lemma}
 The mechanism is monotone.
 \end{lemma}
@@ -395,9 +401,16 @@ The mechanism is budget feasible.
 \end{lemma}
 
 \begin{lemma}
-    Let us denote by $S_M$ the set returned by the mechanism. Then:
+    Let us denote by $S_M$ the set returned by the mechanism. Let us also
+    write:
     \begin{displaymath}
-        V(S_M) \geq ?\cdot OPT(V, \mathcal{N}, B)
+        C_{\textrm{max}} = \max\left(1+C,\frac{e}{e-1}\left( 3 + \frac{12e}{C\cdot
+        C_\mu(e-1) -5e  +1}\right)\right)
+    \end{displaymath}
+
+    Then:
+    \begin{displaymath}
+        V(S_M) \geq C_{\textrm{max}}\cdot OPT(V, \mathcal{N}, B)
     \end{displaymath}
 \end{lemma}
 
@@ -445,8 +458,25 @@ The mechanism is budget feasible.
     \end{displaymath}
 \end{proof}
 
+The optimal value for $C$ is:
+\begin{displaymath}
+    C^* = \arg\min C_{\textrm{max}}
+\end{displaymath}
+
+This equation has two solutions. Only one of those is such that:
+\begin{displaymath}
+    C\cdot C_\mu(e-1) -5e  +1 \geq 0
+\end{displaymath}
+which is a needed in the proof of the previous lemma. Computing this solution,
+we can state the main result of this section.
+
 \begin{theorem}
     The mechanism is individually rational, truthful and has an approximation
-    ratio of
+    ratio of:
+    \begin{multline*}
+        1 + C^* = \frac{5e-1 + C_\mu(4e-1)}{2C_\mu(e-1)}\\
+        + \frac{\sqrt{C_\mu^2(1+2e)^2
+        + 2C_\mu(14e^2+5e+1) + (1-5e)^2}}{2C_\mu(e-1)}
+    \end{multline*}
 \end{theorem}
 \end{document}