--- a/minimum_bisection/paper/preamble.tex	Sat Jul 05 22:50:50 2014 +0200
+++ b/minimum_bisection/paper/preamble.tex	Tue Jul 29 13:56:00 2014 +0200
@@ -27,6 +27,7 @@
 \usepackage[math]{blindtext}
 
 \newcommand{\R}{\mathbb{R}}
+\newcommand{\Rnn}{\mathbb{R}^+_0}
 \newcommand{\Oh}{\mathcal{O}}
 \newcommand{\Ih}{\mathcal{I}}
 \newcommand{\Ell}{\mathcal{L}}
@@ -49,6 +50,7 @@
 \xdefinecolor{tumorange}   {RGB}{227,114, 34}
 \xdefinecolor{tumlightblue}{RGB}{152,198,234}
 
+\newcommand{\define}[1]{\emph{#1}}
 % Dummy commands to reuse beamer code
 \newcommand{\structure}[1]{#1}
 \newcommand{\alert}[1]{#1}

--- a/minimum_bisection/paper/term_paper.bib	Sat Jul 05 22:50:50 2014 +0200
+++ b/minimum_bisection/paper/term_paper.bib	Tue Jul 29 13:56:00 2014 +0200
@@ -32,3 +32,16 @@
   publisher={Cambridge University Press},
   pages={376--385}
 }
+
+@book{intro,
+  added-at = {2012-02-12T20:02:28.000+0100},
+  author = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford},
+  biburl = {http://www.bibsonomy.org/bibtex/2225d42638921bee01b4ac8ff991b0a6a/pvortex3},
+  edition = 2,
+  interhash = {dcdeb0ec50a6798abf1724056982b543},
+  intrahash = {225d42638921bee01b4ac8ff991b0a6a},
+  keywords = {},
+  publisher = {The MIT Press},
+  title = {Introduction to Algorithms},
+  year = 2001
+}

--- a/minimum_bisection/paper/term_paper.tex	Sat Jul 05 22:50:50 2014 +0200
+++ b/minimum_bisection/paper/term_paper.tex	Tue Jul 29 13:56:00 2014 +0200
@@ -17,33 +17,30 @@
 \section{Oblivious Routing}
 \label{sec:oblivious_routing}
 
-\blindtext
-\blindtext
+\define{Maximum Flow} is a well understood algorithmic problem.
+Given a \define{directed graph $G = (V, E)$}, a mapping $c : E \to \Rnn$ denoted by $c_e \defeq c(e)$ assigning a maximum non-negative capacity to every edge and a \define{source} and \define{target} node $s, t \in V$, we are asked to find a flow of maximum value from $s$ to $t$.
+For simplicity, we assume that $G$ is complete, which can be achieved by adding edges of capacity $0$.
+
+\begin{definition}[Flow \cite{intro}]
+    A function $f : E \to \Rnn$ assigning a throughput to every edge.
+    It satisfies the following two properties:
+    \begin{description}
+        \item[Capacity Constraint:] For all $e \in E$, we have $f_e \leq c_e$.
+        \item[Flow Conservation:] For all $v \in V \setminus \left\{ s, t \right\}$, we have 
+            \[\sum_{(u, v) \in E} f_{uv} = \sum_{(v, w) \in E} f_{vw}.\]
+    \end{description}
+    We denote $f_e \defeq f(e)$ for $e \in E$ and $f_{uv} \defeq f(u, v)$ for $u, v \in V$.
+\end{definition}
+
+Maximum Flow problem can be solved in polynomial time using a number of algorithms, for example the Ford-Fulkerson method or Push-relabel algorithms, both of which are described in \cite{intro}.
+
+This paper will introduce a generalization of this problem known as \define{Oblivious Routing} and proof the existence of an $\Oh(\log n)$ approximation scheme based on \cite{racke2008optimal} and described in \cite{approx}.
+After giving a definition of the problem, it is formulated as a linear problem and rewritten to yield the desired algorithm using a theorem giving an $\Oh(\log n)$ approximation of arbitrary metrics using tree metrics.
+Finally, the result is applied to give an $\Oh(\log n)$ approximation of the \define{Minimum Bisection} problem.
 
 \subsection{Problem definition}
 \label{sub:or_problem}
 
-\begin{definition}[Flow]
-    A function $f : E \to \R^+$ assigning a throughput to every edge.
-\end{definition}
-
-\blindtext
-
-\begin{definition}[Congestion]
-    \begin{align}
-        \rho = \max{e \in E} \frac{f_e}{c_e}
-    \end{align}
-\end{definition}
-
-\blindtext
-
-\begin{problem}[Oblivious Routing]
-    Given an undirected Graph $G = (V, E)$ and an edge capacity function $c : E \to \R^+$.
-    Calculate a combination of paths for each $(u, v) \in V^2$ such that for any demand function the congestion will be as small as possible.
-\end{problem}
-
-\blindtext
-
 \begin{figure}[tb]
     \centering
     \begin{tikzpicture}[flow graph]
@@ -80,44 +77,107 @@
 
         \node at (-0.25, 2.4) {$\lambda_{green} = 0.25 \qquad \lambda_{blue} = 0.5 \qquad \lambda_{red} = 0.25$};
     \end{tikzpicture}
-    \caption{Oblivious Routing}
+    \caption{A solution to the oblivious flow problem gives a set of paths and an associated convex combination for any two nodes $u, v \in V$. In this case, we are given the green, blue and red path from $u$ to $v$. The dashed demand $d_{uv}$ gets routed along these three paths, split according to the factors $\lambda_i$.}
     \label{fig:oblivous_routing}
 \end{figure}
 
+To define Oblivious Routing, we first consider a simpler generalization of Maximum Flow, the \define{Multi-Commodity Flow} problem.
+Instead of a single source and target node, we now allow and arbitrary number of nonnegative flow demands between two nodes given by a \define{demand function $d : V^2 \to \Rnn$} on a now undirected graph.
+Every such demand $d(u, v)$ must be routed from $u$ to $v$ using a set of $u$-$v$-paths and the total flow $f_e$ on an edge $e \in E$ is the sum of all demands routed through it.
+The task of is now to find a flow satisfying all demands while exceeding the capacities of all edges as little as possible.
+This excess is called \define{congestion}.
+
+\begin{definition}[Congestion]
+    The congestion $\rho$ attributed to a flow $f$ denotes the smallest factor $\rho$ such that for all edges $e \in E$ we have $f_e \leq \rho \cdot c_e$.
+    \begin{align}
+        \rho = \max_{e \in E} \frac{f_e}{c_e}
+    \end{align}
+\end{definition}
+
+This problem is still solvable in polynomial time using linear programming \cite{approx}.
+One more generalization leads to the oblivious routing problem.
+We now want to find flow solutions without knowing the demands beforehand, i.e. we want to find a set of $u$-$v$-paths and associated fractions of demands for all $u, v \in V$ such that for any demand function this set of paths performs well.
+
+\begin{problem}[Oblivious Routing]
+    Given an undirected Graph $G = (V, E)$ and an edge capacity function $c : E \to \R^+$.
+    Calculate a convex combination of paths for each $(u, v) \in V^2$ such that for any demand function the congestion of the resulting flow will be as small as possible.
+\end{problem}
+
 \subsection{Formulation as a linear program}
 \label{sub:or_lp}
-\blindtext
+
+\begin{figure}[tb]
+    \centering
+    \begin{tikzpicture}[flow graph]
+        \flownodes
+        \flowedges
+        \flowtreeedges
+
+        \begin{pgfonlayer}{background}
+            \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=8pt] (el) {};
+        \end{pgfonlayer}
+
+        \path (el)
+            ++ (200:1)
+            ++ (0, -0.5) coordinate (label);
+        \node[below of = label] {\structure{$S(\alert{e_T})$}};
+
+        \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}
+
+        \begin{pgfonlayer}{marked}
+            \draw[tree edge, tumblue] (m.center) edge (e.center);
+        \end{pgfonlayer}
+        \path (m) -- node[flow capacity]{$e_T$} (e);
+    \end{tikzpicture}
+
+    \caption{Removing the edge $e_T$ from the green spanning tree introduces a tree split. One of the two vertex sets we denote as $S(e_T)$ and define the capacity ot the split as the sum of all capacities of edges crossing the boundary of $S(e_T)$, the blue and orange edges.}
+    \label{fig:tree_splits}
+\end{figure}
+
+To find the desired approximation algorithm, we must first develop some lower bound for the optimal solution.
+A simple idea to create a valid (but probably not optimal) solution is to find any spanning tree $T = (V, E_T)$ of $G$ and route any demand along its edges.
+
+Since it is a spanning tree, there is a unique path from any vertex $u$ to any vertex $v$ in $T$ which will be used to satisfy the complete demand.
+For any edge $e_T \in E_T$ the resulting flow $f_{e_T}$ will be the sum of all demands between two nodes connected by this tree edge.
+These are exactly the nodes in different connected components created by removing the edge $e_T$.
 
 \begin{definition}[Tree Split]
+    Given a tree $T = (V, E_T)$ and an edge $e_T \in E_T$.
+    Removing $e_T$ from $T$ splits it into two connected components, one of which we call $S(e_T)$ and the other one being $V \setminus S(e_T)$.
+
+    We call $C(e_T)$ the capacity and $D(e_T)$ the demand of this split given by the sum of all capacities and demands connecting nodes in different connected components.
     \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}
 \end{definition}
 
-Routing with a spanning tree.
-\begin{align}
-    f(e) &= D(e)
-\end{align}
-Suppose we find
+This definition allows us to write the flow generated by a simple solution to oblivious routing using a spanning tree $T$ as $f_{e_T} = D(e_T)$ for all $e_T \in T$ and $0$ otherwise. We now observe that for a given demand function any solution to the resulting multi-commodity flow problem will be bounded below by all tree splits.
+
+\begin{lemma}
+    \label{lem:optimal}
+    For any tree $T$ and any tree edge $e_T$, any routing in $G$ must contain an edge $e$ with congestion
+    \begin{align}
+        \rho_e \geq \frac{D(e_T)}{C(e_T)}.
+    \end{align}
+    Therefore, the optimal congestion $\rho^\ast$ of the flow problem can be no better.
+\end{lemma}
+
+We will use this observation to proof our approximation guarantee.
+Suppose we find a spanning tree such that every edge has capacity of the capacity of the corresponding tree split times some factor $\alpha \geq 1$.
 \begin{align}
     \forall e_T \in E_T.\quad c_{e_T} &\geq \frac{1}{\alpha} C(e_T)
-    \intertext{Then we have}
+    \intertext{Using \cref{lem:optimal} we can bound the congestion of this spanning tree in relation to the optimal solution.}
     \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}
+Note that this factor $\alpha$ is a property of the tree and not any specific demand function, thus we know that this tree yields a solution of cost at most $\alpha$ times the optimal solution for any demand.
 
-\begin{lemma}
-    For any tree $T$ and any tree edge $e_T$, we know that for any routing in $G$ there must be an edge with congestion
-    \begin{align}
-        \rho_e \geq \frac{D(e_T)}{C(e_T)}
-    \end{align}
-    And therefore the optimal solution $\rho^\ast$ can be no better.
-\end{lemma}
-\begin{proof}
-    \blindtext
-\end{proof}
+This tree does not have to exist however and therefore this approach will not yield any approximation guarantee.
 
 Routing with Spanning Trees.
 \begin{align}
@@ -153,37 +213,6 @@
     \begin{tikzpicture}[flow graph]
         \flownodes
         \flowedges
-        \flowtreeedges
-
-        \begin{pgfonlayer}{background}
-            \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=8pt] (el) {};
-        \end{pgfonlayer}
-
-        \path (el)
-            ++ (200:1)
-            ++ (0, -0.5) coordinate (label);
-        \node[below of = label] {\structure{$S(\alert{e_T})$}};
-
-        \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}
-
-        \begin{pgfonlayer}{marked}
-            \draw[tree edge, tumblue] (m.center) edge (e.center);
-        \end{pgfonlayer}
-        \path (m) -- node[flow capacity]{$e_T$} (e);
-    \end{tikzpicture}
-
-    \caption{Tree splits}
-    \label{fig:tree_splits}
-\end{figure}
-
-\begin{figure}[tb]
-    \centering
-    \begin{tikzpicture}[flow graph]
-        \flownodes
-        \flowedges
 
         \draw
             (l) node[above=3] {\structure{u}}