diff options
| -rw-r--r-- | main.tex | 4 |
1 files changed, 2 insertions, 2 deletions
@@ -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} |