diff options
| author | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-07-03 20:05:28 -0700 |
|---|---|---|
| committer | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-07-03 20:05:28 -0700 |
| commit | 5db33d6a133669cb876f1b4da3c1c1c6fedd0d19 (patch) | |
| tree | 6e74ed072f2b7e33fb7257aa494fb3c775992edb /appendix.tex | |
| parent | 297af7c33e8cc93494cde48212b502f40adc9546 (diff) | |
| download | recommendation-5db33d6a133669cb876f1b4da3c1c1c6fedd0d19.tar.gz | |
approx
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 7 |
1 files changed, 2 insertions, 5 deletions
diff --git a/appendix.tex b/appendix.tex index 67ae7cc..3685c2f 100644 --- a/appendix.tex +++ b/appendix.tex @@ -1,4 +1,3 @@ -\section{Proof of Proposition~\ref{prop:relaxation}} \subsection{Proof of Lemma~\ref{lemma:relaxation-ratio}}\label{proofofrelaxation-ratio} %\begin{proof} @@ -217,9 +216,7 @@ the proof of the lemma. \qed attained at one of its limit, at which either the $i$-th or $j$-th component of $\lambda_\varepsilon$ becomes integral. \end{proof} - -\subsection*{End of the proof of Proposition~\ref{prop:relaxation}} - +\subsection{Proof of Proposition~\ref{prop:relaxation}}\label{proofofproprelaxation} Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*) = L^*_c$. By applying Lemma~\ref{lemma:relaxation-ratio} and Lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most @@ -242,7 +239,7 @@ one fractional component such that \begin{equation}\label{eq:e2} F(\bar{\lambda}) \leq OPT + \max_{i\in\mathcal{N}} V(i). \end{equation} -Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qedhere +Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qed \section{Proof of Proposition~\ref{prop:monotonicity}} |