--- a/minimum_bisection/paper/preamble.tex	Wed Jul 30 15:39:57 2014 +0200
+++ b/minimum_bisection/paper/preamble.tex	Wed Jul 30 16:07:49 2014 +0200
@@ -50,7 +50,7 @@
 \xdefinecolor{tumorange}   {RGB}{227,114, 34}
 \xdefinecolor{tumlightblue}{RGB}{152,198,234}
 
-\newcommand{\define}[1]{\emph{#1}}
+\newcommand{\define}[1]{#1}
 % Dummy commands to reuse beamer code
 \newcommand{\structure}[1]{#1}
 \newcommand{\alert}[1]{#1}

--- a/minimum_bisection/paper/term_paper.tex	Wed Jul 30 15:39:57 2014 +0200
+++ b/minimum_bisection/paper/term_paper.tex	Wed Jul 30 16:07:49 2014 +0200
@@ -20,7 +20,7 @@
 \label{sec:oblivious_routing}
 
 \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$.
+Given a 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}]
@@ -79,13 +79,13 @@
 
         \node at (-0.25, 2.4) {$\lambda_{green} = 0.25 \qquad \lambda_{blue} = 0.5 \qquad \lambda_{red} = 0.25$};
     \end{tikzpicture}
-    \caption{A solution to the oblivious routing 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$.}
+    \caption{A solution to the oblivious routing 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 paths 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.
+Instead of a single source and target node, we now allow an arbitrary number of nonnegative flow demands between two nodes given by a \define{demand function $d : V^2 \to \Rnn$} on an undirected graph.
+Every such demand $d_{uv}$ 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}.
 
@@ -135,7 +135,7 @@
         \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.}
+    \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 of 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}
 
@@ -157,7 +157,7 @@
     \end{align}
 \end{definition}
 
-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.
+This definition illustrated by \cref{fig:tree_splits} 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}
@@ -179,7 +179,7 @@
 \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.
 
-This tree does not have to exist however and therefore this approach will not yield any approximation guarantee.
+This tree however does not have to exist and therefore this approach will not yield any approximation guarantee.
 Since oblivious routing allows us to define multiple $u$-$v$-paths, a natural extension is to consider not only one spanning tree but a convex combination of multiple spanning trees.
 We denote each of these trees as some $T_i = (V, E_{T_i})$ and identify $e \in E_{T_i}$ with $e \in T_i$ for compactness.
 Solutions of this kind are a set of trees and factors $\left\{ (T_i, \lambda_i) \right\}$ with $\lambda_i \geq 0$ and $\sum_i \lambda_i = 1$.
@@ -273,7 +273,7 @@
 \label{sub:or_approx}
 
 To proof the bound for the value of the linear program, we will consider the dual program and show that it is logarithmically bounded.
-The dual problem has exponentially many constraints, one for each path tree, and a decision variable $\ell_{uv}$ for every pair of vertices.
+The dual problem has exponentially many constraints, one for each path tree, and a decision variable $\ell_{uv} \in \Ell$ for every pair of vertices.
 \begin{alignat}{3}
     \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}} \label{eq:dual}\\ %
     \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\
@@ -282,9 +282,9 @@
 \end{alignat}
 
 We will rewrite this dual program to be able to apply a result about the approximation of metrics with tree metrics.
-To this end we will interpret the variables $l_{uv}$ as distances between vertices and obtain a shortest path metric $d_\ell(u, v)$ which we will approximate later. For an edge $e = (x, y)$ we denote $d_\ell(e) \defeq d_\ell(x, y)$.
+To this end we will interpret the variables $\ell_{uv}$ as distances between vertices and obtain a shortest path metric $d_\ell(u, v)$ which we will approximate later. For an edge $e = (x, y)$ we denote $d_\ell(e) \defeq d_\ell(x, y)$.
 
-We first observe that in \cref{eq:dual_constraints} for any given $i$, the length of $P_i(e_T)$ is always at least $d_\ell(e_T)$ and since all constraints bound $z$ above, we can replace the constraints by
+We first observe that in \cref{eq:dual_constraints} for any given $i$, the length of $P_i(e_T)$ is always at least $d_\ell(e_T)$ and since all constraints bound $z$ above and there is some tree choosing the shortest path, we can replace the constraints by
 \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{We can further reduce the constraints to the smallest constraint, again because we are bounding $z$ above.}
@@ -299,7 +299,7 @@
     && \structure{\Ell} &\geq 0
 \end{alignat}
 
-While the non negativity of the distances is actually desired, we now want to show that the last remaining constraint does not in fact reduce the solution space.
+While the nonnegativity of the distances is actually desired, we now want to show that the last remaining constraint does not in fact reduce the solution space.
 Suppose $\sum_{u, v \in V} c_{uv} \ell_{uv} = \beta > 0$, the products of of capacities and lengths sum up to an arbitrary positive value.
 We can then transform the set of lengths $\Ell$ to a feasible solution of the dual problem by scaling every length by $\frac{1}{\beta}$.
 This, however, changes the objective function by the same factor.
@@ -367,17 +367,18 @@
 \end{lemma}
 \begin{proof}
     See \cref{fig:sum_over_capacities}.
+    \qed
 \end{proof}
 
 Combining all observations and lemmas now bounds the value of both linear programs logarithmically, directly following from the logarithmic bound of the tree metrics.
 
-\begin{lemma}
+\begin{theorem}
     The primal and dual linear program have a value of $\Oh(\log n)$.
-\end{lemma}
+\end{theorem}
 \begin{proof}
     We proof the value of the dual program, the value of the primal program then follows by strong duality.
 
-    For any lengths $\Ell$ we know that for the minimizing tree in \cref{eq:dual_compact} we have the following chain of inequalities, using the definition of tree metrics, the previous lemma, and the observation that the distance $d_\ell(u, v)$ is never larger than $\ell_{uv}$ since $d_\ell$ is a shortest path metric.
+    For any lengths $\Ell$ we know that for the minimizing tree in \cref{eq:dual_compact} we have the following chain of inequalities, using the definition of tree metrics, the previous lemma and the observation that the distance $d_\ell(u, v)$ is never larger than $\ell_{uv}$ since $d_\ell$ is a shortest path metric.
     \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} \\
@@ -386,9 +387,10 @@
         \intertext{Dividing by the sum directly gives the value guarantee:}
         \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}
+    \qed
 \end{proof}
 
-While this proofs the existence of a solution of value $\Oh(\log n)$, it still remains to show that polynomially many trees are enough and the solution can actually be found in polynomial time.
+While this proofs the existence of a solution of value $\Oh(\log n)$, it still remains to be shown that polynomially many trees are enough and the solution can actually be found in polynomial time.
 While this is done rigorously in \cite{approx}, the idea is to rewrite the linear program in such a way to not actually search for the minimal $\alpha$ but enforce an $\alpha \in \Oh(\log n)$.
 This results in a linear program which can be solved using the ellipsoid method in polynomial time resulting in a set of polynomially many path trees.
 This then proofs the existence of the desired $\Oh(\log n)$ approximation algorithm.
@@ -434,7 +436,7 @@
 \end{problem}
 
 We will now show that the set of path trees obtained by solving the oblivious flow problem on $G$ with capacity function $c$ contains a tree that defines a bisection of $G$ which costs logarithmically more than an optimal solution.
-We call this bisection a tree bisection.
+We call this bisection a minimum tree bisection.
 It is obtained by reweighing the edges of the tree to cost as much as the tree splits introduced by them and then solving the minimum bisection problem on those trees.
 This can be solved in polynomial time with a straightforward dynamic programming approach described in \cite{approx}.
 
@@ -486,6 +488,7 @@
     While the equality holds by definition, we observe that for every tree edge $e_T$ contained in $\delta(S)$ there must be an edge in $P_i(e_T)$ which crosses the boundary of $S$ since $e_T$ starts in $S$ and ends outside of $S$.
     Therefore, all summands in the left side are contained in the right side, the inequality holds.
     If we apply this for all $T_i$, we have proven the lemma.
+    \qed
 \end{proof}
 
 While we can bound the convex combination of minimum tree bisections obtained by the oblivious flow approximation by the original cost function, we can also show that the original cost is always smaller than the cost of the same set relative to some tree cost function.
@@ -534,6 +537,7 @@
     Since there is an unique path from $u$ to $v$ in $T$ there must be an edge $e_T$ on this path that is also contained in $\delta(S)$.
     But then $(u, v)$ must be contained in the tree split introduced by $e_T$ and is therefore contained in the right hand side costs by definition.
     See \cref{fig:tree_bisections} for an illustration of this proof.
+    \qed
 \end{proof}
 
 These lemmas allow us to quickly prove the approximation guarantee of the algorithm.
@@ -554,6 +558,7 @@
     We now apply \cref{lem:bisection_combination} to show that the original convex combination of bisections is bounded by our desired bound.
     Since the combination of nonnegative costs is bounded, so must be the smallest cost or otherwise the inequality cannot hold.
     This proofs the correctness of the algorithm.
+    \qed
 \end{proof}
 
 \nocite{*}