--- a/minimum_bisection/presentation.tex	Mon May 19 13:37:32 2014 +0200
+++ b/minimum_bisection/presentation.tex	Tue May 20 18:45:32 2014 +0200
@@ -445,9 +445,9 @@
             \begingroup
                 \addtolength{\jot}{.5em}
                 \begin{align}
-                    \structure{\rho} &= \hphantom{\alpha}\max_{\structure{e}} \frac{f(\structure{e})}{c_{\structure{e}}} \\
-                        &\structure{\leq} \alpha \max_{\structure{e}} \frac{\sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(e_T)}} D_i(\alert{e_T})}{\sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(e_T)}} C_i(\alert{e_T})} \\
-                        &\leq \alpha \max_{\structure{e}} \max_{i} \frac{D_i(\structure{e})}{C_i(\structure{e})} \leq \structure{\alpha \rho^\ast}
+                    \rho &= \hphantom{\alpha}\max_{\structure{e}} \frac{f(\structure{e})}{c_{\structure{e}}} \\
+                        &\leq \alpha \max_{\structure{e}} \frac{\sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(e_T)}} D_i(\alert{e_T})}{\sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(e_T)}} C_i(\alert{e_T})} \\
+                        &\leq \alpha \max_{\structure{e}} \max_{i} \frac{D_i(\structure{e})}{C_i(\structure{e})} \leq \alpha \rho^\ast
                 \end{align}
             \endgroup
     \end{itemize}
@@ -462,39 +462,122 @@
 \end{frame}
 
 \begin{frame}
-    \frametitle{Primal Program}
+    \frametitle{Primal program}
 
     \begin{block}{Primal Program}
+        Let $\Ih$ be the exponenitally large set of \structure{all pathtrees}.\\
+        We want to find the best trees with smallest $\alpha$.
         \begin{alignat}{3}
             \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\
-            \st \quad && \sum_i \structure{\lambda_i} \sum_{\substack{e_T \in T_i: \\ \alert{(u, v)} \in P_i(e_T)}} C_i(e_T) & \leq \structure{\alpha} \alert{c_{uv}} & \quad \forall \alert{u,v} \in V \\
-            && \sum_i \structure{\lambda_i} &= 1 \\
+            \st \quad && \sum_{i \in \Ih} \structure{\lambda_i} \sum_{\substack{e_T \in T_i: \\ \alert{(u, v)} \in P_i(e_T)}} C_i(e_T) & \leq \structure{\alpha} \alert{c_{uv}} & \qquad \forall \alert{u,v} \in V \\
+            && \sum_{i \in \Ih} \structure{\lambda_i} &= 1 \\
             && \structure{\lambda} &\geq 0
         \end{alignat}
     \end{block}
+
+    \vfill
+
+    \begin{center}
+        We want to show that $\alpha \in \Oh(\log n)$
+    \end{center}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Dual program}
+
+    \begin{block}{Dual Program}
+        Let $\Ih$ be the exponenitally large set of \structure{all pathtrees}.
+        \begin{alignat}{3}
+            \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ %
+            \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\
+            && \structure{z} & \leq \sum_{e_T \in T_i} C_i(e_T) \sum_{(u,v) \in P_i(e_T)} \structure{\ell_{uv}} & \qquad \forall i \in \Ih \\
+            && \structure{\Ell} &\geq 0
+        \end{alignat}
+    \end{block}
+    \todo{Interpretation of $z$ and $\Ell$}
+
+    \vfill
+
+    \begin{center}
+        If $z \in \Oh(\log n)$ then $\alpha \in \Oh(\log n)$ by strong duality
+    \end{center}
 \end{frame}
 
 \begin{frame}
-    \frametitle{Dual Program}
+    \frametitle{Solution of the dual}
 
     \begin{block}{Dual Program}
+        Let $\Ih$ be the exponenitally large set of \structure{all pathtrees}.
         \begin{alignat}{3}
-            \max_{\structure{\Ell, z}} \quad & \mathrlap{\structure{z}}\\ %
+            \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ %
             \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\
-            && \structure{z} & \leq \sum_{e_T \in T_i} C_i(e_T) \sum_{(u,v) \in P_i(e_T)} \structure{\ell_{uv}} & \quad \forall i \in \Ih \\
+            \only<-2>{
+                && \structure{z} & \leq \sum_{e_T \in T_i} C_i(e_T) \tikzmark{a}\sum_{(u,v) \in P_i(e_T)} \structure{\ell_{uv}} \tikzmark{b} & \qquad \forall i \in \Ih \\
+            }
+            \only<3-4>{
+                && \structure{z} & \leq \tikzmark{c}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)\tikzmark{d} & \qquad \forall i \in \Ih \\
+            }
+            \only<5->{
+                && \structure{z} & \leq \min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)\\
+            }
             && \structure{\Ell} &\geq 0
         \end{alignat}
     \end{block}
+
+    \vfill
+
+    \begin{itemize}
+        \item We interpret the $\ell_{uv}$ as edge lengths in $G$
+        \item They define a \structure{shortest path metric $d_{\structure{\ell}}(u, v)$}
+        \item For an edge $e = (x, y)$ we write $d_{\structure{\ell}}(e) \defeq d_{\structure{\ell}}(x, y)$
+    \end{itemize}
+    \begin{tikzpicture}[remember picture, overlay]
+        \only<2> {%
+            \node[fit=(a)(b), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below:{$\geq d_{\structure{\ell}}(e_T)$}}] {};
+        }
+        \only<4> {%
+            \node[fit=(c)(d), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below right:{$\geq \min_{i \in \Ih} \cdots$}}] {};
+        }
+    \end{tikzpicture}
 \end{frame}
 
 \begin{frame}
-    \frametitle{Proof of $\Oh(\log n)$ness}
+    \frametitle{Solution of the dual}
 
-    \begin{itemize}
-        \item Distance Metric
-        \item Normalization
-        \item inequalities
-    \end{itemize}
+    \begin{block}{Dual Program}
+        Let $\Ih$ be the exponenitally large set of \structure{all pathtrees}.
+        \only<1-2>{%
+            \begin{alignat}{3}
+                \max_{\structure{\Ell}} \quad & \mathrlap{\min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)}\\
+                \st \quad && \tikzmark{a}\sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1\tikzmark{b} \\
+                && \structure{\Ell} &\geq 0
+            \end{alignat}
+            \vspace{-1em}
+        }
+        \only<3>{%
+            \begin{alignat}{3}
+                \max_{\structure{\Ell}} \quad & \min_{i \in \Ih}\frac{\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)}{\sum_{u, v \in V} c_{uv} \structure{\ell{uv}}}\\
+                \st \quad & \structure{\Ell} \geq 0
+            \end{alignat}
+        }
+    \end{block}
+
+    \vfill
+
+    \uncover<2-3>{
+        \begin{itemize}
+            \item Now suppose
+                \begin{align}
+                    \sum_{u, v \in V} c_{uv} \ell_{uv} = \beta > 0
+                \end{align}
+            \item If we scale every length by $\frac{1}{\beta}$ our solution will change by $\frac{1}{\beta}$
+        \end{itemize}
+    }
+    \begin{tikzpicture}[remember picture, overlay]
+        \only<2>{
+            \node[fit=(a)(b), highlight, minimum height=2.5em, inner sep=-3pt] {};
+        }
+    \end{tikzpicture}
 \end{frame}
 
 \begin{frame}
@@ -522,6 +605,12 @@
 \end{frame}
 
 \begin{frame}
+    \frametitle{Inequality Fun \#2}
+
+    content
+\end{frame}
+
+\begin{frame}
     \frametitle{Tree goodness}
 
     content

--- a/minimum_bisection/tikzpictures.tex	Mon May 19 13:37:32 2014 +0200
+++ b/minimum_bisection/tikzpictures.tex	Tue May 20 18:45:32 2014 +0200
@@ -17,6 +17,10 @@
 \tikzstyle{flow capacity} = [node on edge]
 \tikzstyle{flow demand} = [node on edge, text=tumred]
 
+\tikzstyle{highlight} = [draw=tumorange, very thick, rounded corners]
+
+\newcommand{\tikzmark}[1]{\tikz[overlay,remember picture,baseline] \node [anchor=base] (#1) {};}
+
 \newcommand{\flownodes}{%
     \pgfmathsetseed{42}
     \def\jiggliness{0.2}