From a9eb124b9a326104326723e9693ae4779c4df25b Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Mon, 11 Feb 2013 20:45:44 -0800
Subject: edits

---
 main.tex | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 55df8fe..e112470 100644
--- a/main.tex
+++ b/main.tex
@@ -90,9 +90,12 @@ The function $L$ is well-known to be concave and even self-concordant (see
 method for self-concordant functions in \cite{boyd2004convex}, shows that
 finding the maximum of $L$ to any precision $\varepsilon$ can be done in
 $O(\log\log\varepsilon^{-1})$ iterations. Being the solution to a maximization
-problem, $OPT'_{-i^*}$ satisfies the required monotonicity property. The main challenge
+problem, $OPT'_{-i^*}$ satisfies the required monotonicity property. 
+
+The main challenge
 will be to prove that $OPT'_{-i^*}$, for our relaxation $L$, is close to
 $OPT_{-i^*}$. 
+We show this by establishing that $L$ is within a constant factor from the so-called multi-linear relaxation of  \eqref{modified}, which in turn can be related to \eqref{modified} through pipage rounding. We establish the constant factor to the multi-linear relaxation by bounding  the partial derivatives of these two functions; we obtain the latter bound by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices.
 
 \begin{algorithm}[t]
     \caption{Mechanism for \SEDP{}}\label{mechanism}
-- 
cgit v1.2.3-70-g09d2

