From 5db33d6a133669cb876f1b4da3c1c1c6fedd0d19 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Wed, 3 Jul 2013 20:05:28 -0700 Subject: approx --- appendix.tex | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-) (limited to 'appendix.tex') 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}} -- cgit v1.2.3-70-g09d2