From 6f255bcbe303748bfface378be199cb9d9b5012f Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sat, 6 Jul 2013 20:32:20 -0700
Subject: sherman morisson

---
 appendix.tex | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

(limited to 'appendix.tex')

diff --git a/appendix.tex b/appendix.tex
index 3c2fed8..5dce278 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -178,7 +178,7 @@ the proof of the lemma. \qed
 \subsection{Proof of Lemma~\ref{lemma:rounding}}\label{proofoflemmarounding}
 %\begin{proof}
     We give a rounding procedure which, given a feasible $\lambda$ with at least
-    two fractional components, returns some feasible $\lambda'$ with one less fractional
+    two fractional components, returns some feasible $\lambda'$ with one fewer fractional
     component such that $F(\lambda) \leq F(\lambda')$.
 
     Applying this procedure recursively yields the lemma's result.
@@ -284,7 +284,7 @@ contains the strictly feasible point $\lambda=(\frac{1}{n},\ldots,\frac{1}{n})$.
     is the right-hand side  of the lemma.
     For the left-hand side, note that $\tilde{A}(\lambda) \preceq A_n$. Hence
     $\partial_iL(\lambda)\geq \T{x_i}A_n^{-1}x_i$.
-    Using the Sherman-Morrison formula, for all $k\geq 1$:
+    Using the Sherman-Morrison formula \cite{sm}, for all $k\geq 1$:
     \begin{displaymath}
         \T{x_i}A_k^{-1} x_i = \T{x_i}A_{k-1}^{-1}x_i 
         - \frac{(\T{x_i}A_{k-1}^{-1}x_k)^2}{1+\T{x_k}A_{k-1}^{-1}x_k}
@@ -325,7 +325,7 @@ Similarly, we define $\mathcal{L}_{c}\defeq\mathcal{L}_{c, 0}$ the lagrangian of
 
 Let $\lambda^*$ be primal optimal for \eqref{eq:perturbed-primal}, and $(\mu^*,
 \nu^*, \xi^*)$ be dual optimal for the same problem. In addition to primal and
-dual feasibility, the KKT conditions give $\forall i\in\{1, \ldots, n\}$:
+dual feasibility, the Karush-Kuhn-Tucker (KKT) conditions \cite{boyd2004convex} give $\forall i\in\{1, \ldots, n\}$:
 \begin{gather*}
     \partial_i L(\lambda^*) + \mu_i^* - \nu_i^* - \xi^* c_i = 0\\
     \mu_i^*(\lambda_i^* - \alpha) = 0\\
@@ -616,7 +616,7 @@ OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
 \end{displaymath}
 \end{lemma}
 
-Using Proposition~\ref{prop:relaxation} and~\ref{lemma:greedy-bound} we can complete the proof of
+Using Proposition~\ref{prop:relaxation} and Lemma~\ref{lemma:greedy-bound} we can complete the proof of
 Theorem~\ref{thm:main} by showing that, for any $\varepsilon > 0$, if
 $OPT_{-i}'$, the optimal value of $L$ when $i^*$ is excluded from
 $\mathcal{N}$, has been computed to a precision $\varepsilon$, then the set
@@ -660,7 +660,7 @@ Thus, if $C$ is such that $C(e-1) -6e  +2 > 0$,
 \end{align*}
 Finally, using Lemma~\ref{lemma:greedy-bound} again, we get
 \begin{equation}\label{eq:bound2}
-    OPT(V, \mathcal{N}, B) \leq 
+    OPT \leq 
     \frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}\right) V(S_G)
     + \frac{2e\varepsilon}{C(e-1)- 6e + 2}.
 \end{equation}
-- 
cgit v1.2.3-70-g09d2

