--- a/minimum_bisection/presentation.tex	Sun May 18 00:49:24 2014 +0200
+++ b/minimum_bisection/presentation.tex	Sun May 18 14:07:58 2014 +0200
@@ -109,45 +109,219 @@
 \end{frame}
 
 \begin{frame}
-    \frametitle{Oblivious Routing}
+    \frametitle{Routing with a Spanning Tree}
+
+    \begin{itemize}
+        \item Choose any \structure{spanning tree $T$} of $G$
+        \item Routing along its unique paths is a feasible solution
+        \item But probably not a good one
+    \end{itemize}
+
+    \vfill
+
+    \centering
+    \begin{tikzpicture}[flow graph]
+        \flownodes
+        \flowedges
+        \flowtreeedges
 
-    \begin{center}
-        \begin{tikzpicture}[flow graph]
-            \flownodes
-            \flowedges
-            \flowtreeedges
+        \only<2-> {
+            \draw
+                (l) node[above right] {\structure{u}}
+                (i) node[above right] {\structure{v}};
+            \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i);
+        }
+
+        \only<3-> {
+            \begin{pgfonlayer}{marked}
+                \foreach \source/ \dest in {l/m,m/e,e/d,d/k,k/j,j/i}
+                \draw[tree edge, tumred] (\source.center) edge (\dest.center);
+            \end{pgfonlayer}
+        }
+
+        \only<4-> {
             \flowcapacities
-            \flowdemands
-
-            \begin{pgfonlayer}{background}
-                \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(g)(i)(k)(j), inner sep=3pt] {};
-            \end{pgfonlayer}
-        \end{tikzpicture}
-    \end{center}
+            \node[below=0.2 of b] {\structure{$\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{10}{2} = 5$}};
+        }
+    \end{tikzpicture}
 \end{frame}
 
 \begin{frame}
-    \frametitle{Definitions}
+    \frametitle{Tree Splits}
 
     \begin{itemize}
-        \item Graph
-        \item Spanning Tree
-        \item Cut
-        \item Demand
-        \item Congestion
+        \item Removing one edge $e_T$ from a ST creates a \structure{node partition $S(e_T)$}
+        \item Every such partition has a \structure{capacity $C(e_T)$}
+        \item And a \structure{demand $D(e_T)$}
+    \end{itemize}
+    \begin{align}{}
+        C(e_T) &= \sum_{\substack{u \in S(e_T), \\ v  \not\in S(e_T)}} c_{uv} &
+        D(e_T) &= \sum_{\substack{u \in S(e_T), \\ v  \not\in S(e_T)}} c_{uv}
+    \end{align}
+
+    \centering
+    \begin{tikzpicture}[flow graph]
+        \flownodes
+        \flowedges
+        \flowtreeedges
+
+        \only<2-> {
+            \begin{pgfonlayer}{marked}
+                \draw[tree edge, tumred] (m.center) edge (e.center);
+            \end{pgfonlayer}
+
+            \begin{pgfonlayer}{background}
+                \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=3pt] (el) {};
+            \end{pgfonlayer}
+
+            \path (el)
+                ++ (200:1.5)
+                ++ (0, -0.5) coordinate (label);
+            \node[below=0 of label] {\structure{$S(\alert{e_T})$}};
+        }
+
+        \only<3> {
+            \flowcapacities
+
+            \begin{pgfonlayer}{marked}
+                \foreach \source/ \dest in {l/h,m/e,m/f,n/b}
+                \draw[tree edge, tumorange] (\source.center) edge (\dest.center);
+            \end{pgfonlayer}
+        }
+
+        \only<3-> {
+            \node[below=0.5 of label] {$C(e_T) = 10$};
+        }
+
+        \only<4-> {
+            \flowdemands
+
+            \begin{pgfonlayer}{demand}
+                \foreach \source/\dest/\demand/\pos/\bendage in {
+                    {n/j/10/0.2/right},
+                    {n/h/12/0.7/left},
+                    {k/m/5/0.8/right}}
+                \draw[demand edge, bend \bendage=15, tumorange] (\source) edge node[flow demand, text=tumorange, pos=\pos]{\demand} (\dest);
+            \end{pgfonlayer}
+
+            \node[below=1 of label] {$D(e_T) = 27$};
+        }
+    \end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Optimal solution}
+
+    \begin{lemma}
+        For any tree $T$ and any tree edge $e_T$, we know that for \alert{any routing} in $G$ there must be an edge with \structure{congestion}
+        \begin{align}
+            \rho_e \geq \frac{D(e_T)}{C(e_T)}
+        \end{align}
+        And therefore the \structure{optimal solution $\rho^\ast$} can be no better.
+    \end{lemma}
+
+    \vfill
+    \pause
+
+    \begin{itemize}
+        \item Suppose we find a tree such that for some $\alpha$
+            \begin{align}
+                \forall e_T \in E_T.\quad c_{e_T} \geq \frac{1}{\alpha} C(e_T)
+            \end{align}
+        \item Then we have
+            \begin{align}
+                \structure{\rho_T} = \max_{e_T} \frac{D(e_T)}{c_{e_T}} \structure{\leq} \alpha \max_{e_T} \frac{D(e_T)}{C(e_T)} \leq \structure{\alpha \rho^\ast}
+            \end{align}
     \end{itemize}
 \end{frame}
 
 \begin{frame}
-    \frametitle{Routing with a Tree}
+    \frametitle{Routing with multiple spanning trees}
+
+    \begin{itemize}
+        \item Choose a \structure{set of spanning trees $\left\{ T_i \right\}$} of $G$
+        \item And a \structure{convex combination $\lambda$} with $\sum_i \lambda_i = 1$, $\lambda \geq 0$
+        \item Routing is now split according to this combination. For $e \in E$
+            \begin{align}
+                f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)
+            \end{align}
+    \end{itemize}
+
+    \vfill
+
+    \centering
+    \begin{tikzpicture}[flow graph]
+        \flownodes
+        \flowedges
+
+        \draw
+            (l) node[above right] {\structure{u}}
+            (i) node[above right] {\structure{v}};
+        \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i);
+
+        \path
+            (n)
+            ++ (-1, -0.5) coordinate (label);
 
-    content
+        \only<2> {
+            \flowtreeedges
+        }
+
+        \only<2-> {
+            \node[tumgreen, below=0 of label, anchor=west] {$\lambda_1 = \frac{1}{2}$};
+        }
+
+        \only<3> {
+            \flowtreeedgestwo[tumorange]
+        }
+
+        \only<3-> {
+            \node[tumorange, below=0.5 of label, anchor=west] {$\lambda_2 = \frac{1}{2}$};
+        }
+
+        \only<4-> {
+            \begin{pgfonlayer}{marked}
+                \foreach \source/ \dest in {l/m,m/e,e/d,d/k,k/j,j/i}
+                \draw[tree edge, tumgreen] (\source.center) edge (\dest.center);
+            \end{pgfonlayer}
+
+            \begin{pgfonlayer}{marked}
+                \foreach \source/ \dest in {l/h,h/i}
+                \draw[tree edge, tumorange] (\source.center) edge (\dest.center);
+            \end{pgfonlayer}
+        }
+
+        \only<5-> {
+            \flowcapacities
+            \node[below=1 of label, anchor=west] {\structure{$\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{5}{2} = 2.5$}};
+        }
+    \end{tikzpicture}
 \end{frame}
 
 \begin{frame}
-    \frametitle{Routing with convex Combinations}
+    \frametitle{Routing with multiple spanning trees}
 
-    content
+    \begin{itemize}
+        % \item Remember that the total flow on edge $e \in E$ is
+        %     \begin{align}
+        %         f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)
+        %     \end{align}
+        \item Suppose we now find a \structure{set of trees} such that for some $\alpha$
+            \begin{align}
+                \forall e \in E.\quad c_{e} \geq \frac{1}{\alpha} \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)
+            \end{align}
+        \vfill
+        \item Then we have
+            \begingroup
+                \addtolength{\jot}{.5em}
+                \begin{align}
+                    \structure{\rho} &= \hphantom{\alpha}\max_{e} \frac{f(e)}{c_{e}} \\
+                        &= \hphantom{\alpha}\max_{e} \frac{\sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)}{c_e} \\
+                        &\structure{\leq} \alpha \max_{e} \frac{\sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)}{\sum_{\substack{i:\\e \in T_i}} \lambda_i C_i(e)} \\
+                        &\leq \alpha \max_{e} \max_{i} \frac{D_i(e)}{C_i(e)} \leq \structure{\alpha \rho^\ast}
+                \end{align}
+            \endgroup
+    \end{itemize}
 \end{frame}
 
 \begin{frame}

--- a/minimum_bisection/tikzpictures.tex	Sun May 18 00:49:24 2014 +0200
+++ b/minimum_bisection/tikzpictures.tex	Sun May 18 14:07:58 2014 +0200
@@ -81,8 +81,17 @@
             % {a/b},
             {c/b},
             {c/d}, {e/d}, {e/f}, {g/i},
-            {h/e}, {h/i}, {i/j}, {k/j},
-            {l/h}, {l/m}, {n/m}}
+            {m/e}, {d/k}, {i/j}, {k/j},
+            {h/i}, {l/m}, {n/m}}
         \draw[tree edge, #1] (\source.center) edge (\dest.center);
     \end{pgfonlayer}
 }
+\newcommand{\flowtreeedgestwo}[1][]{%
+    \begin{pgfonlayer}{marked}
+        \foreach \source/ \dest in {
+            {n/l}, {l/h}, {h/i}, {i/g}, {i/j},
+            {j/k}, {g/d}, {d/c}, {g/e}, {c/f},
+            {f/m}, {f/b}}
+        \draw[tree edge, #1] (\source.center) edge (\dest.center);
+    \end{pgfonlayer}
+}