diff options
Diffstat (limited to 'proofs.tex')
| -rw-r--r-- | proofs.tex | 29 |
1 files changed, 18 insertions, 11 deletions
@@ -6,10 +6,12 @@ budget feasibility follow the same steps as the analysis of \citeN{chen}; for the sake of completeness, we restate their proof in the Appendix. The complexity of the mechanism is given by the following lemma. + \begin{lemma}[Complexity]\label{lemma:complexity} For any $\varepsilon > 0$, the complexity of the mechanism is $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. \end{lemma} + \begin{proof} The value function $V$ in \eqref{modified} can be computed in time $O(\text{poly}(n, d))$ and the mechanism only involves a linear @@ -50,11 +52,12 @@ OPT \end{equation} To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to $\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume -that on line 3 of algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that +that on line 3 of Algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq OPT_{-i^*}' \leq \tilde{L}+\varepsilon$ has been computed (Lemma~\ref{lemma:complexity} states that this is computed in time -within our complexity guarantee). If the condition on line 3 of the algorithm -holds, then: +within our complexity guarantee). + +If the condition on line 3 of the algorithm holds, then: \begin{displaymath} V(i^*) \geq \frac{1}{C}OPT_{-i^*}'-\frac{\varepsilon}{C} \geq \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C} @@ -64,20 +67,24 @@ hence: \begin{equation}\label{eq:bound1} OPT\leq (1+C)V(i^*) + \varepsilon \end{equation} -Note that $OPT_{-i^*}'\leq OPT'$. If the condition does not hold, from Lemmas -\ref{lemma:relaxation} and \ref{lemma:greedy-bound}: -\begin{align*} - V(i^*) & \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C} - \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\ - & \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G) + +If the condition does not hold, by observing that $OPT'_{-i^*}\leq OPT'$ and +applying Lemma~\ref{lemma:relaxation}, we get: +\begin{displaymath} + V(i^*) \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C} + \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C} +\end{displaymath} +Applying Lemma~\ref{lemma:greedy-bound}: +\begin{displaymath} + V(i^*) \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G) + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C} -\end{align*} +\end{displaymath} Thus, if $C$ is such that $C(e-1) -6e +2 > 0$, \begin{align*} V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2} \end{align*} -Finally, using again Lemma~\ref{lemma:greedy-bound}, we get: +Finally, using Lemma~\ref{lemma:greedy-bound} again, we get: \begin{equation}\label{eq:bound2} OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e +2}\right) V(S_G) |