diff options
| -rw-r--r-- | general.tex | 14 |
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} |