--- a/minimum_bisection/paper/preamble.tex	Sat Jul 05 20:25:20 2014 +0200
+++ b/minimum_bisection/paper/preamble.tex	Sat Jul 05 22:50:50 2014 +0200
@@ -6,9 +6,9 @@
 \usepackage[utf8]{inputenc}
 
 \usepackage{amsmath}
+\usepackage{amssymb}
 \usepackage{mathdots}
 \usepackage{mathtools}
-\mathtoolsset{showonlyrefs,showmanualtags}
 \usepackage{mathrsfs}
 \usepackage{csquotes}
 
@@ -23,6 +23,9 @@
 \usepackage[pdftex]{hyperref}
 \usepackage[nameinlink, capitalize]{cleveref}
 
+% \newcommand{\blindtext}{Blindtext!}
+\usepackage[math]{blindtext}
+
 \newcommand{\R}{\mathbb{R}}
 \newcommand{\Oh}{\mathcal{O}}
 \newcommand{\Ih}{\mathcal{I}}
@@ -49,3 +52,8 @@
 % Dummy commands to reuse beamer code
 \newcommand{\structure}[1]{#1}
 \newcommand{\alert}[1]{#1}
+
+% LLNCS algorithms
+\makeatletter
+\spn@wtheorem{algorithm}{Algorithm}{\bfseries}{\itshape}
+\makeatother

--- a/minimum_bisection/paper/term_paper.tex	Sat Jul 05 20:25:20 2014 +0200
+++ b/minimum_bisection/paper/term_paper.tex	Sat Jul 05 22:50:50 2014 +0200
@@ -11,13 +11,39 @@
 \maketitle
 \thispagestyle{plain}
 \begin{abstract}
-  I am an abstract!
+    \blindtext
 \end{abstract}
 
 \section{Oblivious Routing}
 \label{sec:oblivious_routing}
+
+\blindtext
+\blindtext
+
 \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]
@@ -60,6 +86,67 @@
 
 \subsection{Formulation as a linear program}
 \label{sub:or_lp}
+\blindtext
+
+\begin{definition}[Tree Split]
+    \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
+\begin{align}
+    \forall e_T \in E_T.\quad c_{e_T} &\geq \frac{1}{\alpha} C(e_T)
+    \intertext{Then we have}
+    \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}
+
+\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}
+
+Routing with Spanning Trees.
+\begin{align}
+    f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)
+    \intertext{suppose we find}
+    \forall e \in E.\quad c_{e} &\geq \frac{1}{\alpha} \sum_{\substack{i:\\e \in T_i}} \lambda_i C_i(e)
+    \intertext{then}
+    \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}
+
+\begin{definition}[Path Tree]
+    A path tree of an undirected graph $G = (V, E)$ is a pair $(T, P)$ of a spanning tree $T$ of $G$ and a function $P : E_T \to E$ identifiing every edge $e_T = (x, y)$ of $T$ with a path in $G$ from $x$ to $y$.
+\end{definition}
+
+Routing with Path trees.
+\begin{align}
+    f(\structure{e}) &= \sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(\alert{e_T})}} D_i(\alert{e_T})
+\end{align}
+\begin{align}
+    \forall \structure{e} \in E.\quad c_{e} \geq \frac{1}{\alpha} \sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(\alert{e_T})}} C_i(\alert{e_T})
+\end{align}
+\begin{align}
+    \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}
 
 \begin{figure}[tb]
     \centering
@@ -144,12 +231,78 @@
 
 Dual
 \begin{alignat}{3}
-    \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ %
+    \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}} \label{eq:dual}\\ %
     \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{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 \label{eq:dual_constraints}\\
+    && \structure{\Ell} &\geq 0
+\end{alignat}
+
+Rewrite \cref{eq:dual_constraints}
+\begin{align}
+    \structure{z} & \leq \sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T) \qquad \forall i \in \Ih\\
+    \intertext{And again}
+    \structure{z} & \leq \min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)
+\end{align}
+
+To get
+\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}
 
+Suppose $\sum_{u, v \in V} c_{uv} \ell_{uv} = \beta > 0$, then the solution changes by the same factor.
+Thus rewrite finally
+\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}}} \label{eq:dual_compact}\\
+    \st \quad & \structure{\Ell} \geq 0
+\end{alignat}
+
+Then we use from \cite{approx}.
+\begin{theorem}[Tree Metric]
+    For any nonnegative set of costs $c_{uv}$ and any metric $d_\ell$ there exists a tree metric $(V, M)$ such that
+    \begingroup
+        \addtolength{\jot}{.5em}
+        \begin{alignat}{2}
+            d_\ell(u, v) &\leq M_{uv} & \forall u, v \in V\\
+            \sum_{u, v \in V} c_{uv} M_{uv} &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v).
+        \end{alignat}
+    \endgroup
+\end{theorem}
+
+\blindtext
+
+\begin{lemma}
+    Let $T$ be a spanning tree and $(V, M)$ a tree metric of $G = (V, E)$. Then we can rewrite the sum over all edges of $T$ in \cref{eq:dual_compact} as a sum over all edges in $G$.
+    \begin{align}
+        \sum_{(x, y) \in E_T} C(x, y) M_{xy} = \sum_{(u, v) \in E} c_{uv} M_{uv}
+    \end{align}
+\end{lemma}
+\begin{proof}
+    \blindtext
+\end{proof}
+
+\begin{lemma}
+    The linear program has a value of $\Oh(\log n)$.
+\end{lemma}
+\begin{proof}
+    For any $\Ell$ we know that for the \structure{minimizing tree $T_i$} holds
+    \begin{align}
+        \sum_{e_T \in T_i} C_i(e_T) d_\ell(e_T) &\leq \sum_{e_T \in T_i} C_i(e_T) M_{e_T} \\
+        &= \sum_{u, v \in V} c_{uv} M_{uv} \\
+        &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v) \\
+        &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} \ell_{uv} \\
+        \frac{\sum_{e_T \in T_i} C_i(e_T) d_\ell(e_T)}{\sum_{u, v \in V} c_{uv} \ell_{uv}} &\leq \Oh(\log n)
+    \end{align}
+\end{proof}
+
+\begin{theorem}
+    There is an $\Oh(\log n)$ approximation algorithm for the minimum bisection problem.
+\end{theorem}
+\begin{proof}
+    Use the upper guarantee, then apply ellipsoid method.
+\end{proof}
+
 \begin{figure}[tb]
     \centering
     \begin{tikzpicture}[flow graph]
@@ -186,8 +339,30 @@
 
 \section{Minimum Bisection}
 \label{sec:minimum_bisection}
+\blindtext
+
 \subsection{Problem definition}
 \label{sub:mb_problem}
+\begin{problem}[Minimum Bisection]
+    Given an undirected Graph $G = (V, E)$ and an edge-cost function $c : E \to \R^+$.
+    Find a set $S \subset V$ containing half the vertices with \structure{minimal split cost}.
+\end{problem}
+
+\blindtext
+
+\begin{definition}[Tree Bisection]
+    Given a spanning tree $T$ of $G$ with an edge $e_T \in E_T$.
+    We define a new cost function $c_T : E_T \to \R^+$ based on the tree splits induced by the edges of $T$.
+    The cost of a bisection $S$ is the sum of tree split costs of all tree edges cut by $S$.
+    \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}
+    The tree bisection of $T$ is an optimal solution of the minimum bisection problem with respect to the cost function $c_T$.
+\end{definition}
+
+\blindtext
+
 \begin{figure}[tb]
     \centering
     \begin{tikzpicture}[flow graph]
@@ -212,6 +387,65 @@
 
 \subsection{Approximation using oblivious routing}
 \label{sub:mb_approx}
+
+\begin{algorithm}
+    \label{alg:minimum_bisection}
+    Given graph $G = (V, E)$ and cost function $c : E \to \R^+$.
+    \begin{enumerate}
+        \item Interpret costs $c(e)$ as capacities
+        \item Solve oblivious routing on $G$, obtaining trees $T_i$
+        \item Find minimum tree bisections $X_i$ for all trees $T_i$
+        \item Choose the $X_i$ with lowest $c(\delta(X_i))$
+    \end{enumerate}
+\end{algorithm}
+
+\begin{lemma}
+    For any spanning tree $T$ and any cut $S \subseteq V$ the cost of the cut is bounded above by the tree bisection of $T$.
+    \begin{align}
+        c(\delta(S)) \leq c_T(\delta(S))
+    \end{align}
+\end{lemma}
+\begin{proof}
+    \blindtext
+\end{proof}
+
+\blindtext
+
+\begin{lemma}
+    Let $\left\{ (T_i, \lambda_i) \mid i \in \Ih \right\}$ be a $\Oh(\log n)$-approximation to the oblivious flow problem.
+    Then for any cut $S \subseteq V$ the convex combination of tree bisections is bounded above by the cost of $S$ times a logarithmic factor.
+    \begin{align}
+        \sum_i \lambda_i c_{T_i}(\delta(S)) \leq \Oh(\log n) c(\delta(S))
+    \end{align}
+\end{lemma}
+\begin{proof}
+    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}
+    We sum up the inequalities for all $(u, v) \in \delta(S)$.
+    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}
+    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{proof}
+
+\begin{theorem}
+    \cref{alg:minimum_bisection} is an $\Oh(\log n)$ approximation algorithm for the minimum bisection problem.
+\end{theorem}
+\begin{proof}
+    \blindtext
+    \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}
+\end{proof}
+
 \begin{figure}[tb]
     \begin{tikzpicture}[flow graph]
         \flownodes