diff options
| -rw-r--r-- | slides/BudgetFeasibleExperimentalDesign.tex | 20 |
1 files changed, 17 insertions, 3 deletions
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 |