--- a/minimum_bisection/preamble.tex	Sat May 17 16:44:50 2014 +0200
+++ b/minimum_bisection/preamble.tex	Sun May 18 00:49:24 2014 +0200
@@ -19,11 +19,8 @@
 \usepackage{tikz}
 \usepackage{pgfplots}
 \pgfplotsset{compat=1.8}
-\usetikzlibrary{automata}
-\usetikzlibrary{calc}
 \usetikzlibrary{shapes}
-\usetikzlibrary{positioning}
-\usetikzlibrary{chains}
+\usetikzlibrary{fit}
 
 \usepackage{amsmath}
 \usepackage{mathdots}
@@ -44,6 +41,8 @@
 \newcommand{\C}{\mathbb{C}}
 \newcommand{\Prob}{\mathrm{P}}
 \newcommand{\Oh}{\mathcal{O}}
+\newcommand{\Ih}{\mathcal{I}}
+\newcommand{\Ell}{\mathcal{L}}
 
 \newcommand{\abs}[1]{\left\vert #1 \right\vert}
 \newcommand{\powerset}[1]{\mathcal{P}\left( #1 \right)}
@@ -52,13 +51,4 @@
 
 \newcommand{\defeq}{\coloneqq} %Mathtools already defines this
 
-\pgfdeclarelayer{background}
-\pgfdeclarelayer{foreground}
-\pgfsetlayers{background,main,foreground}
-
-\tikzstyle{edge} = [draw,very thick,->,>=latex]
-\tikzstyle{pretty} = [circle,thick,draw,fill=tumblue!10]
-\tikzstyle{every edge} = [edge]
-\tikzstyle{every state} = [pretty]
-\tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
-\tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\Huge]
+\DeclareMathOperator{\st}{s.t.}

--- a/minimum_bisection/presentation.tex	Sat May 17 16:44:50 2014 +0200
+++ b/minimum_bisection/presentation.tex	Sun May 18 00:49:24 2014 +0200
@@ -1,4 +1,5 @@
 \input{preamble.tex}
+\input{tikzpictures.tex}
 
 \title{Oblivious Routing and Minimum Bisection}
 \subtitle{Approximation Algorithms Seminar}
@@ -10,4 +11,221 @@
     \titlepage
 \end{frame}
 
+\begin{frame}
+    \frametitle{Flow Problems}
+    \begin{problem}[Single Commodity Flow]
+        Given
+        \begin{itemize}[<+->]
+            \item An (un)directed Graph $G = (V, E)$
+            \item A \structure{capacity function} $c : E \to \R^+$
+            \item A source $s$ and a target $t$
+        \end{itemize}
+        \uncover<4->{Calculate the maximum possible \structure{flow} $f : E \to \R^+$ through $G$.}
+    \end{problem}
+
+    \centering
+    \begin{tikzpicture}[flow graph]
+        \flownodes
+        \flowedges[directed]
+        \only<2->{\flowcapacities}
+
+        \draw<3->
+            (n.south) node[below] {\structure{s}}
+            (j.south) node[below] {\structure{t}};
+    \end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Flow Problems}
+
+    \begin{problem}[Multi Commodity Flow]
+        Given
+        \begin{itemize}
+            \item An undirected Graph $G = (V, E)$
+            \item A capacity function $c : E \to \R^+$
+            \item<2-> A \structure{demand function} $d : V^2 \to \R^+$
+        \end{itemize}
+        \uncover<3->{Calculate the flow $f$ with least \structure{congestion $\rho = \max_{e \in E}\frac{f_e}{c_e}$}.}
+    \end{problem}
+
+    \centering
+    \begin{tikzpicture}[flow graph]
+        \flownodes
+        \flowedges
+        \flowcapacities
+        \only<2->{\flowdemands}
+    \end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Oblivious Routing}
+
+    \begin{problem}[Oblivious Routing]
+        Given
+        \begin{itemize}
+            \item An undirected Graph $G = (V, E)$
+            \item A capacity function $c : E \to \R^+$
+        \end{itemize}
+        Calculate a combination of paths for each $(u, v) \in V^2$ such that for \alert{any} demand function the \structure{congestion} will be as small as possible.
+    \end{problem}
+
+    \centering
+    \begin{tikzpicture}[flow graph]
+        \flownodes
+        \flowedges
+        \flowcapacities
+
+        \draw<2->
+            (n.south) node[below] {\structure{u}}
+            (j.south) node[below] {\structure{v}};
+
+        \only<3-> {
+            \begin{pgfonlayer}{marked}
+                \draw[marked edge, tumgreen]
+                    (n.center) edge (l.center)
+                    (l.center) edge (h.center)
+                    (h.center) edge (i.center)
+                    (i.center) edge (j.center);
+
+                \draw[marked edge, tumblue]
+                    (n.center) edge (m.center)
+                    (m.center) edge (e.center)
+                    (e.center) edge (c.center)
+                    (c.center) edge (k.center)
+                    (k.center) edge (j.center);
+
+                \draw[marked edge, tumred]
+                    (n.center) edge (b.center)
+                    (b.center) edge (j.center);
+            \end{pgfonlayer}
+
+            \path[font=\Large]
+                (n)
+                +(-0.5, 0.5) node[tumgreen] {$\frac{1}{4}$}
+                +(-0.5, 0) node[tumblue] {$\frac{1}{2}$}
+                +(-0.5, -0.5) node[tumred] {$\frac{1}{4}$};
+        }
+    \end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Oblivious Routing}
+
+    \begin{center}
+        \begin{tikzpicture}[flow graph]
+            \flownodes
+            \flowedges
+            \flowtreeedges
+            \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}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Definitions}
+
+    \begin{itemize}
+        \item Graph
+        \item Spanning Tree
+        \item Cut
+        \item Demand
+        \item Congestion
+    \end{itemize}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Routing with a Tree}
+
+    content
+\end{frame}
+
+\begin{frame}
+    \frametitle{Routing with convex Combinations}
+
+    content
+\end{frame}
+
+\begin{frame}
+    \frametitle{Routing with convex Combinations and Pathtrees}
+
+    content
+\end{frame}
+
+\begin{frame}
+    \frametitle{Primal Program}
+
+    \begin{block}{Primal Program}
+        \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 \\
+            && \structure{\lambda} &\geq 0
+        \end{alignat}
+    \end{block}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Dual Program}
+
+    \begin{block}{Dual Program}
+        \begin{alignat}{3}
+            \max_{\structure{\Ell, z}} \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 \\
+            && \structure{\Ell} &\geq 0
+        \end{alignat}
+    \end{block}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Proof of $\Oh(\log n)$ness}
+
+    \begin{itemize}
+        \item Distance Metric
+        \item Normalization
+        \item inequalities
+    \end{itemize}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Polynomial Algorithm}
+
+    content
+\end{frame}
+
+\begin{frame}
+    \frametitle{Minimum Bisection Problem}
+
+    content
+\end{frame}
+
+\begin{frame}
+    \frametitle{Solution Algorithm}
+
+    content
+\end{frame}
+
+\begin{frame}
+    \frametitle{Inequality Fun \#2}
+
+    content
+\end{frame}
+
+\begin{frame}
+    \frametitle{Tree goodness}
+
+    content
+\end{frame}
+
+\begin{frame}
+    \frametitle{Solution of MB on trees}
+
+    content
+\end{frame}
+
 \end{document}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/minimum_bisection/tikzpictures.tex	Sun May 18 00:49:24 2014 +0200
@@ -0,0 +1,88 @@
+\pgfdeclarelayer{background}
+\pgfdeclarelayer{demand}
+\pgfdeclarelayer{marked}
+\pgfdeclarelayer{foreground}
+\pgfsetlayers{background,demand,marked,main,foreground}
+
+\tikzstyle{edge} = [thick]
+\tikzstyle{marked edge} = [edge, line width=3pt, tumorange]
+\tikzstyle{directed} = [arrows={-latex}, shorten >=1pt]
+\tikzstyle{node on edge} = [fill=white, circle, inner sep=1pt, font=\footnotesize]
+
+\tikzstyle{flow graph} = [x=4em, y=5em]
+\tikzstyle{flow node} = [circle, draw, thick, fill=tumblue!20, minimum size=6pt, inner sep=0pt]
+\tikzstyle{flow edge} = [edge]
+\tikzstyle{demand edge} = [edge, line width=2.5pt, arrows={-latex}, dotted, tumred!50]
+\tikzstyle{tree edge} = [marked edge, tumgreen]
+\tikzstyle{flow capacity} = [node on edge]
+\tikzstyle{flow demand} = [node on edge, text=tumred]
+
+\newcommand{\flownodes}{%
+    \pgfmathsetseed{42}
+    \def\jiggliness{0.2}
+    \def\jiggle{++ (random * \jiggliness, random * \jiggliness)}
+
+    \path[use as bounding box] (-4, 2.7) rectangle (3.5,6.15);
+
+    \foreach \pos/\name in {
+        % {(0,1)/a},
+        {(-0.5,2.75)/b},
+        {(0.5,3.25)/c},
+        {(0.75,4)/d},
+        {(-0.5,4.5)/e},
+        {(-1.25,3.75)/f},
+        {(1.5,4.75)/g},
+        {(0,5.5)/h},
+        {(2.5,5.5)/i},
+        {(3.5,3.5)/j},
+        {(2.25,4)/k},
+        {(-2,6)/l},
+        {(-2.5,5)/m},
+        {(-4,5)/n}}
+    \draw \pos\jiggle node[flow node] (\name) {};
+    % \draw \pos\jiggle node[flow node, label={\name}, font=\footnotesize] (\name) {};
+}
+\newcommand{\flowedges}[1][]{%
+    \foreach \source/\dest in {
+        % {a/b}, {a/n}, {a/j},
+        {n/b}, {b/j}, {f/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},
+        {c/k}, {k/i}, {g/d}, {m/e}, {n/l},
+        {m/f}, {f/c}, {d/k}, {e/g}, {c/e}}
+    \draw[flow edge, #1] (\source) edge (\dest);
+}
+\newcommand{\flowcapacities}[1][]{%
+    \foreach \source/\dest/\capacity in {
+        % {a/b}, {a/n}, {a/j},
+        {n/b/2}, {b/j/10}, {c/b/3}, {f/b/4},
+        {c/d/1}, {e/d/2}, {e/f/4}, {g/i/2},
+        {h/e/1}, {h/i/2}, {i/j/6}, {k/j/4},
+        {l/h/3}, {l/m/3}, {n/m/5},
+        {c/k/4}, {k/i/3}, {g/d/1}, {m/e/4}, {n/l/6},
+        {m/f/1}, {f/c/2}, {d/k/4}, {e/g/1}, {c/e/5}}
+    \path (\source) -- node[flow capacity, #1]{\capacity} (\dest);
+}
+\newcommand{\flowdemands}{%
+    \begin{pgfonlayer}{demand}
+        \foreach \source/\dest/\demand/\pos/\bendage in {
+            {n/j/10/0.2/right},
+            {h/j/8/0.2/left},
+            {e/g/1/0.7/left},
+            {n/h/12/0.7/left},
+            {k/m/5/0.8/right}}
+        \draw[demand edge, bend \bendage=15] (\source) edge node[flow demand, pos=\pos]{\demand} (\dest);
+    \end{pgfonlayer}
+}
+\newcommand{\flowtreeedges}[1][]{%
+    \begin{pgfonlayer}{marked}
+        \foreach \source/ \dest in {
+            % {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}}
+        \draw[tree edge, #1] (\source.center) edge (\dest.center);
+    \end{pgfonlayer}
+}