diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 12 |
1 files changed, 4 insertions, 8 deletions
@@ -70,13 +70,11 @@ c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b) We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}: \begin{theorem}\label{thm:main} \sloppy - For any $\delta>0$ the allocation described in Algorithm~\ref{mechanism}, - along with threshold payments, is $\delta$-truthful, individually rational - and budget feasible. Furthermore, there exists an absolute constant $C$ - such that, for any $\varepsilon>0$, the mechanism runs in time + For any $\delta>0$, and any $\epsilon>0$, there exists a $\delta$-truthful, individually rational + and budget feasible mechanim for \EDP{} that runs in time $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$ and returns - a set $S^*$ such that: + a set $S^*$ such that % \begin{align*} $ OPT \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+ @@ -84,9 +82,7 @@ We can now state our main result, which is proved in Appendix~\ref{sec:proofofma \simeq 12.98V(S^*) + \varepsilon.$ % \end{align*} \end{theorem} -The value of the constant $C$ is given by \eqref{eq:constant} in -Appendix~\ref{sec:proofofmainthm}. -In addition, we prove the following simple lower bound. +In addition, we prove the following simple lower bound, proved in Appendix~\ref{proofoflowerbound}. \begin{theorem}\label{thm:lowerbound} There is no $2$-approximate, truthful, budget feasible, individually rational |