summaryrefslogtreecommitdiffstats
path: root/main.tex
diff options
context:
space:
mode:
authorStratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>2012-11-05 00:41:57 -0800
committerStratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>2012-11-05 00:41:57 -0800
commit64b5cb571172477e68c8a16862a29ec617292677 (patch)
treec85ce30482a0b0596f68acab7c4feb31d0ca059a /main.tex
parentf837faec68d1a34ba57dc847888810fd4836291b (diff)
downloadrecommendation-64b5cb571172477e68c8a16862a29ec617292677.tar.gz
optl
Diffstat (limited to 'main.tex')
-rw-r--r--main.tex4
1 files 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}