From a9a63ce0c0f152df3a8c50abe852bf61617b72b7 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 8 Jul 2013 18:36:10 +0200
Subject: Fix theorem for non-homotropic prior

---
 general.tex | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

(limited to 'general.tex')

diff --git a/general.tex b/general.tex
index 87475a4..b219247 100644
--- a/general.tex
+++ b/general.tex
@@ -15,15 +15,17 @@ analysis of the approximation ratio \emph{mutatis mutandis}, we get the followin
 Theorem~\ref{thm:main}. 
 
 \begin{theorem}
- There exists a truthful, individually rational and budget feasible mechanism for the objective
- function $V$ given by \eqref{dcrit}. Furthermore, for any $\varepsilon
- > 0$, in time $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$,
- the algorithm computes a set $S^*$ such that:
+ For any $\delta>0$, there exists a $\delta$-truthful, individually rational
+ and budget feasible mechanism for the objective function $V$ given by
+ \eqref{dcrit}. Furthermore, let us denote by $\lambda$ (resp. $\Lambda$) the
+ smallest (resp. largest) eigenvalue of $R$, then for any $\varepsilon > 0$, in time
+ $O(\text{poly}(n, d, \log\log\frac{B\Lambda}{\varepsilon\delta b\lambda}))$,
+ the mechanism computes a set $S^*$ such that:
  \begin{displaymath}
     OPT \leq 
-    \frac{5e-1}{e-1}\frac{2\mu}{\log(1+\mu)}V(S^*) + 5.1 + \varepsilon
+    \bigg(\frac{6e-2}{e-1}\frac{1/\lambda}{\log(1+1/\lambda)}+ 4.66\bigg)V(S^*)
+    + \varepsilon.
 \end{displaymath}
-where $\mu$ is the smallest eigenvalue of $R$.
 \end{theorem}
 
 \subsection{Non-Bayesian Setting}
-- 
cgit v1.2.3-70-g09d2

