diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 12 |
1 files changed, 4 insertions, 8 deletions
@@ -289,25 +289,21 @@ Its proof is our main technical contribution, and can be found in Section \ref{s Let $x^*\in [0,1]^{n-1}$ be the true maximizer of $L_{\mathcal{N}\setminus\{i^*\}}$ subject to the budget constraints. Assume that on line 2 of algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq L_{\mathcal{N}\setminus {i^*}}(x^*) \leq \tilde{L}+\varepsilon$ has been computed (lemma~\ref{lemma:complexity} - states that this can be done in a time within our complexity guarantee). - + states that this is computed in time within our complexity guarantee). If the condition on line 3 of the algorithm holds, then: \begin{displaymath} V(i^*) \geq \frac{1}{C}L(x^*)-\frac{\varepsilon}{C} \geq - \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B) + \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B) -\frac{\varepsilon}{C} \end{displaymath} - - But: + as $L$ is a fractional relaxation of $V$ on $\mathcal{N}\setminus \{i^*\}$. Also, \begin{displaymath} OPT(V,\mathcal{N},B) \leq OPT(V,\mathcal{N}\setminus\{i\}, B) + V(i^*) \end{displaymath} - Hence: \begin{equation}\label{eq:bound1} OPT(V,\mathcal{N}, B)\leq (1+C)V(i^*) + \varepsilon \end{equation} - - If the condition of the algorithm does not hold, by applying lemmas + If the condition of the algorithm does not hold, by applying Lemmas \ref{lemma:relaxation} and \ref{lemma:greedy-bound}: \begin{align*} V(i^*) & \leq \frac{1}{C}L(x^*) + \frac{\varepsilon}{C}\leq \frac{1}{C} |