From 232a91e5359ae2e924f7777159ec62f4a9dcf3c4 Mon Sep 17 00:00:00 2001 From: Thibaut Horel 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(-) 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