Merge branch 'master' of ssh://palosgit01/git/data_value

1 files changed, 8 insertions, 6 deletions

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}