diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 7 |
1 files changed, 5 insertions, 2 deletions
@@ -367,7 +367,7 @@ Hence, the total payment is bounded by the telescopic sum: \end{proof} Finally, we prove the approximation ratio of the mechanism. We use the -following lemma which we prove later, which establishes that $OPT'$, the optimal value \eqref{relax} of the fractional relaxation $L$ under the budget constraints +following lemma which establishes that $OPT'$, the optimal value \eqref{relax} of the fractional relaxation $L$ under the budget constraints is not too far from $OPT$. \begin{lemma}\label{lemma:relaxation} %\begin{displaymath} @@ -375,9 +375,12 @@ following lemma which we prove later, which establishes that $OPT'$, the optimal + 2\max_{i\in\mathcal{N}}V(i)$ %\end{displaymath} \end{lemma} +The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}. + + +\paragraph{Finishing Proof of } Note that the lower bound $OPT' \geq OPT $ also holds trivially, as $L$ is a fractional relaxation of $V$ over $\mathcal{N}$. -The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}. Using this lemma, we can complete the proof of Theorem~\ref{thm:main} by showing that, %\begin{lemma}\label{lemma:approx} %C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C %(e-1) -10e +2}\right)\right) |