--- a/minimum_bisection/paper/term_paper.tex	Wed Jul 30 14:27:59 2014 +0200
+++ b/minimum_bisection/paper/term_paper.tex	Wed Jul 30 15:39:57 2014 +0200
@@ -396,25 +396,6 @@
 \section{Minimum Bisection}
 \label{sec:minimum_bisection}
 
-The knowledge about the existence of an $\Oh(\log n)$ approximation algorithm for the oblivious routing problem
-
-\begin{problem}[Minimum Bisection]
-    Given an undirected Graph $G = (V, E)$ and an edge-cost function $c : E \to \Rnn$.
-    Find a set $S \subset V$ containing half the vertices with \structure{minimal split cost}.
-\end{problem}
-
-
-\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 \Rnn$ 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}
-
 \begin{figure}[tb]
     \centering
     \begin{tikzpicture}[flow graph]
@@ -433,10 +414,44 @@
             \draw [tree edge, tumorange] (\source.center) -- (\dest.center);
         \end{pgfonlayer}
     \end{tikzpicture}
-    \caption{Minimum Bisection}
+    \caption{The cost $c(\delta(S))$ of the bisection $S$ is defined as the sum of the nonnegative costs of all orange edges leaving the set $S$.}
     \label{fig:minimum_bisection}
 \end{figure}
 
+The knowledge about the existence of an $\Oh(\log n)$ approximation algorithm for the oblivious routing problem can be applied to find approximation algorithms for a number of other problems, some of which are described in \cite{racke2008optimal}.
+As an example, we will now give a definition of the minimum bisection problem and show that it can be approximated using oblivious flow.
+
+Minimum bisection has a similar structure to oblivious flow as it is also defined over undirected graphs with a function mapping the edges to non negative numbers.
+Instead of interpreting these numbers as a capacity, they are now understood as costs.
+We want to find a set containing half of the vertices such that the sum of all costs of edges leaving this set is minimal.
+\begin{problem}[Minimum Bisection]
+    Given an undirected Graph $G = (V, E)$ and an edge-cost function $c : E \to \Rnn$.
+    Find a set $S \subset V$ containing half the vertices with minimal split cost $c(\delta(S))$.
+    \begin{align}
+        \delta(S) &\defeq \left\{ (x, y) \in E \mid x \in S \wedge y \not\in S \right\} \\
+        c(\delta(S)) &\defeq \sum_{\substack{e \in E:\\e \in \delta(S)}} c_e
+    \end{align}
+\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.
+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}.
+
+\begin{definition}[Minimum 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 \Rnn$ 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 minimum tree bisection $X$ of $T$ is an optimal solution of the minimum bisection problem with respect to the cost function $c_T$.
+\end{definition}
+
+Assuming we can find minimum tree bisections in polynomial time, the following algorithm describes an $\Oh(\log n)$ approximation algorithm for the minimum bisection problem.
+While the polynomial running time is clear, it remains to show that the obtained solution actually satisfies the approximation guarantee.
+
 \begin{algorithm}
     \label{alg:minimum_bisection}
     Given graph $G = (V, E)$ and cost function $c : E \to \Rnn$.
@@ -448,48 +463,32 @@
     \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}
-\end{proof}
+To proof the guarantee we will need two lemmas connecting the cost of a split in the original graph $G$ with the costs in a single spanning tree $T$ relative to its cost function $c_T$ and a convex combination of trees.
 
 \begin{lemma}
-    Let $\left\{ (T_i, \lambda_i) \mid i \in \Ih \right\}$ be a $\Oh(\log n)$-approximation to the oblivious flow problem.
+    \label{lem:bisection_combination}
+    Let $\left\{ (T_i, \lambda_i) \right\}$ be an $\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
+    We remember the first constraint of the primal program in \cref{eq:primal}.
+    Since we have already proven that $\alpha \in \Oh(\log n)$ we can replace it by this bound and sum up the inequalities for all edges in $\delta(S)$.
     \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
+    The right hand side then sums up to the desired term, while we have to rewrite the left hand side a bit.
     \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}
+    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.
 \end{proof}
 
-\begin{theorem}
-    \cref{alg:minimum_bisection} is an $\Oh(\log n)$ approximation algorithm for the minimum bisection problem.
-\end{theorem}
-\begin{proof}
-    \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}
+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.
 
 \begin{figure}[tb]
     \begin{tikzpicture}[flow graph]
@@ -519,10 +518,44 @@
         \foreach \source/\dest/\name in {b/c/$e_3$,e/f/$e_2$,e/m/$e_1$}
         \path (\source) -- node[node on edge] {\name} (\dest);
     \end{tikzpicture}
-    \caption{Costs are lower as tree costs}
+    \caption{The cost of $S$ in the original graph is the sum of all red and blue dashed edge costs. While the red edges are tree edges and thus contained in the tree cost function, the blue dashed edge connecting $u$ and $v$ is contained in the tree split introduced by edge $e_3$ on the tree path between $u$ and $v$.}
     \label{fig:tree_bisections}
 \end{figure}
 
+\begin{lemma}
+    \label{lem:bisection_single}
+    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}
+    An edge $(u, v)$ is contained in $\delta(S)$ iff it starts in $S$ and ends outside of $S$.
+    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.
+\end{proof}
+
+These lemmas allow us to quickly prove the approximation guarantee of the algorithm.
+
+\begin{theorem}
+    \cref{alg:minimum_bisection} is an $\Oh(\log n)$ approximation algorithm for the minimum bisection problem.
+\end{theorem}
+\begin{proof}
+    Let $X^\ast$ be an optimal minimum bisection of $G$ and $\left\{ (T_i, \lambda_i) \right\}$ be a set of trees obtained from the oblivious flow algorithm with minimum tree bisections $X_i$.
+    We consider the convex combination of the costs of all minimum tree bisections.
+    \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^\ast) \\
+        &\leq \Oh(\log n) c(\delta(X^\ast))
+    \end{align}
+    Using \cref{lem:bisection_single} we know that every single tree bisection $X_i$ can only cost more relative to its respective cost function $c_{T_i}$.
+    But since the $X_i$ are optimal solutions for the trees $T_i$, the global optimal solution $X^\ast$ cannot be better.
+    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.
+\end{proof}
+
 \nocite{*}
 \bibliographystyle{alpha}
 \bibliography{term_paper}