From a06ec5611efa6f08bcf6782c0657e2d04a47c3e2 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Fri, 26 Oct 2012 11:50:47 -0700
Subject: More details

---
 paper.tex | 20 +++++++++++++++++---
 1 file changed, 17 insertions(+), 3 deletions(-)

(limited to 'paper.tex')

diff --git a/paper.tex b/paper.tex
index 4d02cad..55e7209 100644
--- a/paper.tex
+++ b/paper.tex
@@ -229,6 +229,16 @@ problem. Explain the goals:
 
 \section{Main result}
 
+Explain:
+\begin{itemize}
+    \item the mechanism uses the greedy heuristic
+    \item we know that the maximum of greedy and meatiest guy is a good
+    approximation, but not incentive compatible
+    \item instead compare the value of the meatiest guy to $L(x^*)$ (introduce
+    $L(x^*)$ which can be easily computed and is not too far from the greedy
+    value
+\end{itemize}
+
 \begin{algorithm}\label{mechanism}
     \caption{Mechanism for ridge regression}
     \begin{algorithmic}[1]
@@ -251,11 +261,15 @@ problem. Explain the goals:
     \end{algorithmic}
 \end{algorithm}
 
-Choosing $C=...$ we have:
-
 \begin{theorem}
     The mechanism is truthful, individually rational, budget feasible.
-    Furthermore, by choosing $C= ...$ we get an approximation ratio of:
+    Furthermore, choosing:
+    \begin{multline*}
+        C = C^* =  \frac{5e-1 + C_\mu(2e+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*}
+    we get an approximation 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
-- 
cgit v1.2.3-70-g09d2