From aac827337cae6769113b06fe589cbe4ea7c6028b Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Mon, 4 Mar 2013 19:06:20 -0800
Subject: proof steps

---
 slides/BudgetFeasibleExperimentalDesign.tex | 20 +++++++++++++++++---
 1 file changed, 17 insertions(+), 3 deletions(-)

(limited to 'slides/BudgetFeasibleExperimentalDesign.tex')

diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex
index cc8a1a6..bb39ebd 100644
--- a/slides/BudgetFeasibleExperimentalDesign.tex
+++ b/slides/BudgetFeasibleExperimentalDesign.tex
@@ -732,14 +732,28 @@ $L(\lambda^*)$ is:
            % \vspace{0.5cm}
             \begin{block}{Technical Lemma}
                 \begin{displaymath}
-                    L(\lambda^*) \leq 2 OPT + V(\{i^*\})
+                    L(\lambda^*) \leq 2 OPT + 2V(\{i^*\})
                 \end{displaymath}
             \end{block}
     \end{itemize}
-   \pause
-    Proved by showing that $L(\lambda)\leq 2 F(\lambda)$, where $F$ the multilinear relaxation of $V$. %using \emph{pipage rounding} [Ageev and Sviridenko 2004]
+%   \pause
+%    Proved by showing that $L(\lambda)\leq 2 F(\lambda)$, where $F$ the multilinear relaxation of $V$. %using \emph{pipage rounding} [Ageev and Sviridenko 2004]
 \end{frame}
 
+\begin{frame}{Proof Steps}
+           \begin{block}{Technical Lemma}
+                \begin{displaymath}
+                    L(\lambda^*) \leq 2 OPT + 2V(\{i^*\})
+                \end{displaymath}
+            \end{block}
+\uncover<2->{For all $\lambda\in [0,1]^N$, we show that $L(\lambda) \leq 2F(\lambda)$, where $F$ the multi-linear relaxation of $V$.\\
+\bigskip}
+\uncover<3->{
+We show this by establishing first that $\frac{\partial_i F(\lambda)}{\partial_i L(\lambda)}\geq \frac{1}{2}$, and arguing about the minima of $\frac{F(\lambda)}{L(\lambda)}$ over the simplex.\\
+\bigskip
+}
+\uncover<4>{Finally, we show that $F(\lambda^*)\leq OPT+V(\{i^*\})$ through pipage rounding.}
+\end{frame}
 \begin{comment}
     \vspace{0.5cm}
     \pause
-- 
cgit v1.2.3-70-g09d2

