diff options
Diffstat (limited to 'general.tex')
| -rw-r--r-- | general.tex | 15 |
1 files 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^*) |