From 232a91e5359ae2e924f7777159ec62f4a9dcf3c4 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 8 Jul 2013 18:56:05 +0200
Subject: Fix wording of theorem 3

---
 general.tex | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)

(limited to 'general.tex')

diff --git a/general.tex b/general.tex
index b219247..2e7312e 100644
--- a/general.tex
+++ b/general.tex
@@ -10,17 +10,18 @@ model $\beta$ in \eqref{model} is not homotropic and has a generic covariance
 matrix $R$, the value function takes the general form given by
 \eqref{dcrit}.
 
-Applying the mechanism described in Algorithm~\ref{mechanism} and adapting the
-analysis of the approximation ratio \emph{mutatis mutandis}, we get the following result which extends
+Let us denote by $\lambda$ (resp. $\Lambda$) the smallest (resp. largest)
+eigenvalue of $R$, applying the mechanism described in
+Algorithm~\ref{mechanism} and adapting the analysis of the approximation ratio
+\emph{mutatis mutandis}, we get the following result which extends
 Theorem~\ref{thm:main}. 
 
 \begin{theorem}
- For any $\delta>0$, there exists a $\delta$-truthful, individually rational
+ For any $\delta\in(0,1]$, and any $\epsilon\in(0,1]$, 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:
+ \eqref{dcrit} that runs in time
+ $O(\text{poly}(n, d, \log\log\frac{B\Lambda}{\varepsilon\delta b\lambda}))$
+ and allocates a set $S^*$ such that:
  \begin{displaymath}
     OPT \leq 
     \bigg(\frac{6e-2}{e-1}\frac{1/\lambda}{\log(1+1/\lambda)}+ 4.66\bigg)V(S^*)
-- 
cgit v1.2.3-70-g09d2

