--- a/minimum_bisection/presentation.tex	Wed May 21 18:02:50 2014 +0200
+++ b/minimum_bisection/presentation.tex	Wed May 21 22:45:24 2014 +0200
@@ -114,11 +114,12 @@
     \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
+        \item The flow is defined by the demands of the splits. For $e_T \in E_T$
+            \begin{align}
+                f(e_T) &= D(e_T)
+            \end{align}
     \end{itemize}
 
-    \vfill
-
     \centering
     \begin{tikzpicture}[flow graph]
         \flownodes
@@ -156,7 +157,7 @@
         \item Every such partition has a \structure{capacity $C(e_T)$}
         \item And a \structure{demand $D(e_T)$}
     \end{itemize}
-    \begin{align}{}
+    \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}
@@ -795,39 +796,217 @@
 
     \begin{itemize}
         \item There is a $\structure{\lambda}$ such that $\structure{\alpha \in \Oh(\log n)}$
-        \item The algorithm as an \alert{$\Oh(\log n)$-approximation}
+        \item The algorithm is an \alert{$\Oh(\log n)$-approximation}
         \item But why are polynomially many trees enough?
     \end{itemize}
 \end{frame}
 
 \begin{frame}
-    \frametitle{Minimum Bisection Problem}
+    \frametitle{Minimum Bisection}
+
+    \begin{problem}[Minimum Bisection]
+        Given
+        \begin{itemize}
+            \item An undirected Graph $G = (V, E)$
+            \item A cost function $c : E \to \R^+$
+        \end{itemize}
+        Find a set $S \subset V$ containing half the vertices with \structure{minimal split cost}.
+    \end{problem}
+
+    \vfill
+
+    \centering
+    \begin{tikzpicture}[flow graph]
+        \flownodes
+        \flowedges
+        \flowcapacities
 
-    content
+        \only<2-> {
+            \begin{pgfonlayer}{background}
+                \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {};
+            \end{pgfonlayer}
+
+            \path (el)
+                ++ (-30:2.3) node {\structure{$S$}};
+        }
+
+        \only<3-4> {
+            \begin{pgfonlayer}{marked}
+                \foreach \source/\dest in {b/j,b/c,c/f,e/c,e/d,e/g,h/i}
+                \draw [tree edge, tumorange] (\source.center) -- (\dest.center);
+            \end{pgfonlayer}
+
+            \path (n)
+                ++ (-0.5, -1.5) node[tumorange, anchor=west] {\alt<3>{$\hphantom{c(}\delta(S)$}{$c(\delta(S)) = 25$}};
+        }
+    \end{tikzpicture}
 \end{frame}
 
 \begin{frame}
-    \frametitle{Solution Algorithm}
+    \frametitle{Approximation Algorithm}
 
-    content
+    \begin{block}{Minimum Bisection Approximation}
+        Given graph $G = (V, E)$ and cost function $c : E \to \R^+$.
+        \begin{enumerate}
+            \item Interpret costs $c(e)$ as \structure{capacities}
+            \item Solve oblivious routing on $G$, obtaining \structure{trees $T_i$}
+            \item Find minimum \structure{tree bisections $X_i$} for all trees $T_i$
+            \item Choose the $X_i$ with \structure{lowest $c(\delta(X_i))$}
+        \end{enumerate}
+    \end{block}
+
+    \vfill
+    \pause
+
+    We have to show
+    \begin{itemize}
+        \item What the $X_i$ actually are
+        \item An \alert{$\Oh(\log n)$-approximation} guarantee
+        \item That we can find the $X_i$ in polynomial time
+    \end{itemize}
 \end{frame}
 
 \begin{frame}
-    \frametitle{Inequality Fun \#2}
+    \frametitle{Tree bisections}
+
+    \begin{itemize}
+        \item Given a spanning tree $T$ of $G$ with an edge $e_T \in E_T$
+        \item Define a new \structure{cost function $c_T$} using tree splits
+    \end{itemize}
+    \begin{align}
+        c_T(e_T) &= C(e_t) & c_T(\delta(S)) = \sum_{\substack{e_T \in E_T:\\e_T \in \delta(S)}} C(e_T)
+    \end{align}
+
+    \vfill
+
+    \centering
+    \begin{tikzpicture}[flow graph]
+        \flownodes
+        \flowedges
+        \flowtreeedges
 
-    content
+        \only<2-> {
+            \begin{pgfonlayer}{background}
+                \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {};
+            \end{pgfonlayer}
+
+            \path (el)
+                ++ (-30:2.3) node {\structure{$S$}};
+        }
+
+        \only<3> {
+            \begin{pgfonlayer}{marked}
+                \foreach \source/\dest in {b/c,e/d,h/i}
+                \draw [tree edge, tumred] (\source.center) -- (\dest.center);
+            \end{pgfonlayer}
+
+            \foreach \source/\dest/\name in {b/c/$e_3$,e/d/$e_2$,h/i/$e_1$}
+            \path (\source) -- node[node on edge] {\name} (\dest);
+
+            \path (n)
+                ++ (-1, -1.5) node[tumred, anchor=west] {$\displaystyle c_T(\delta(S)) = \sum_{k=1}^3 C(e_k)$};
+        }
+    \end{tikzpicture}
 \end{frame}
 
 \begin{frame}
-    \frametitle{Inequality Fun \#2}
+    \frametitle{Tree bisections}
+
+    \begin{lemma}[]
+        For any tree $T$ and any $S \subseteq V$ we have
+        \begin{align}
+            c(\delta(S)) \leq c_T(\delta(S))
+        \end{align}
+    \end{lemma}
+
+    \vfill
+
+    \centering
+    \begin{tikzpicture}[flow graph]
+        \flownodes
+        \flowedges
+        \flowtreeedges
 
-    content
+        \begin{pgfonlayer}{background}
+            \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {};
+        \end{pgfonlayer}
+
+        \path (el)
+            ++ (-30:2.3) node {\structure{$S$}};
+
+        \begin{pgfonlayer}{marked}
+            \foreach \source/\dest in {b/j,f/c,e/c,e/g}
+            \draw [tree edge, tumblue, dash pattern=on 7pt off 7pt] (\source.center) -- (\dest.center);
+
+            \foreach \source/\dest in {b/c,e/d,h/i}
+            \draw [tree edge, tumred] (\source.center) -- (\dest.center);
+        \end{pgfonlayer}
+
+        \foreach \source/\dest/\name in {b/c/$e_3$,e/d/$e_2$,h/i/$e_1$}
+        \path (\source) -- node[node on edge] {\name} (\dest);
+    \end{tikzpicture}
 \end{frame}
 
 \begin{frame}
-    \frametitle{Tree goodness}
+    \frametitle{Tree Bisections}
+
+    \begin{lemma}[]
+        Let $\left\{ T_i \right\}$ be a solution to the \structure{oblivious flow} problem on $G$.\\
+        Then for any $S \subseteq V$ we have
+        \begin{align}
+            \sum_i \lambda_i c_{T_i}(\delta(S)) \leq \Oh(\log n) c(\delta(S))
+        \end{align}
+    \end{lemma}
+
+    \vfill
 
-    content
+    \begin{itemize}
+        \only<1> {
+            \item Remember from the primal program that \structure{for all $u, v \in V$}
+                \begin{align}
+                    \sum_i \lambda_i \sum_{\substack{e_T \in T_i:\\\structure{(u,v)} \in P_i(e_T)}} C_i(e_T) \leq \Oh(\log n) \structure{c_{uv}}
+                \end{align}
+            \item We sum up the inequalities for all $(u, v) \in \delta(S)$
+        }
+        \only<2> {
+            \item We sum up the inequalities for all $(u, v) \in \delta(S)$
+            \item This gives us
+                \begin{align}
+                    \sum_i \lambda_i \sum_{\structure{(u, v) \in \delta(S)}} \sum_{\substack{e_T \in T_i:\\\structure{(u,v)} \in P_i(e_T)}} C_i(e_T) \leq \Oh(\log n)c(\delta(S))
+                \end{align}
+            \item We are done with the observation that
+                \begin{align}
+                    c_{T_i}(\delta(S)) = \sum_{\substack{e_T \in E_{T_i}:\\e_T \in \delta(S)}} C_i(e_T) \leq \sum_{\structure{(u, v) \in \delta(S)}} \sum_{\substack{e_T \in T_i:\\\structure{(u,v)} \in P_i(e_T)}} C_i(e_T)
+                \end{align}
+        }
+    \end{itemize}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Approximation Algorithm}
+
+    \begin{block}{Minimum Bisection Approximation}
+        Given graph $G = (V, E)$ and cost function $c : E \to \R^+$.
+        \begin{enumerate}
+            \item Interpret costs $c(e)$ as \structure{capacities}
+            \item Solve oblivious routing on $G$, obtaining \structure{trees $T_i$}
+            \item Find minimum \structure{tree bisections $X_i$} for all trees $T_i$
+            \item Choose the $X_i$ with \structure{lowest $c(\delta(X_i))$}
+        \end{enumerate}
+    \end{block}
+
+    \vfill
+
+    \begin{itemize}
+        \item Let now $X^*, X_i$ be the optimal solutions on $G$ and the $T_i$. Then
+            \begin{align}
+                \sum_i \lambda_i c(\delta(X_i)) &\leq \sum_i \lambda_i c_{T_i}(\delta(X_i)) \\
+                &\leq \sum_i \lambda_i c_{T_i}(\delta(X^*)) \\
+                &\leq \Oh(\log n) c(\delta(X^*))
+            \end{align}
+        \item This also holds for the \structure{best $X_i$}
+        \item How to find the $X_i$?
+    \end{itemize}
 \end{frame}
 
 \end{document}