From 64b5cb571172477e68c8a16862a29ec617292677 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Mon, 5 Nov 2012 00:41:57 -0800 Subject: optl --- main.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/main.tex b/main.tex index 269bc7a..4fa6e74 100644 --- a/main.tex +++ b/main.tex @@ -282,7 +282,7 @@ following lemma, which establishes that $OPT'$, the optimal value \eqref{relax} + 2\max_{i\in\mathcal{N}}V(i)$ %\end{displaymath} \end{lemma} -Note that the lower bound $OPT(L, B) \geq OPT +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} @@ -605,7 +605,7 @@ Having bound the ratio between the partial derivatives, we now bound the ratio $ function $V$. Hence, the ratio is equal to 1 on the vertices. \end{proof} To prove Lemma~\ref{lemma:relaxation}, let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*) - = OPT(L, B)$. By applying Lemma~\ref{lemma:relaxation-ratio} + = OPT'$. By applying Lemma~\ref{lemma:relaxation-ratio} and Lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most one fractional component such that: \begin{equation}\label{eq:e1} -- cgit v1.2.3-70-g09d2