--- a/minimum_bisection/paper/term_paper.tex	Tue Jul 29 18:17:10 2014 +0200
+++ b/minimum_bisection/paper/term_paper.tex	Tue Jul 29 18:49:41 2014 +0200
@@ -188,15 +188,6 @@
     f_e &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)
 \end{align}
 where we denote the demand of the split introduced by $T_i$ using some edge $e \in T_i$ as $D_i(e)$.
-Suppose we find a set of trees such that
-\begin{align}
-    \forall e \in E.\quad c_{e} &\geq \frac{1}{\alpha} \sum_{\substack{i:\\e \in T_i}} \lambda_i C_i(e),
-    \intertext{we can again bound its congestion by the optimal solution using \cref{lem:optimal}.}
-    \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}
 
 This solution scheme is still too strict though and we want to allow more sophisticated structures.
 Instead of using the spanning trees directly, we interpret every node on a $u$-$v$-path of $T_i$ as an intermediate point on a path from $u$ to $v$.
@@ -258,7 +249,7 @@
 If we again suppose to find a set of path trees such that
 \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})
-    \intertext{we get the now familiar bound, again using \cref{lem:optimal}.}
+    \intertext{we can again bound its congestion by the optimal solution using \cref{lem:optimal}.}
     \rho &= \hphantom{\alpha}\max_{\structure{e}} \frac{f_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
@@ -317,51 +308,6 @@
     \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]
@@ -392,10 +338,52 @@
             \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=8pt] (el) {};
         \end{pgfonlayer}
     \end{tikzpicture}
-    \caption{Sum over all Capacities}
+    \caption{
+To proof the desired approximation guarantee we now approximate $d_\ell$ using a result obtained about tree metrics from \cite{approx}.
+To proof the desired approximation guarantee we now approximate $d_\ell$ using a result obtained about tree metrics from \cite{approx}.
+To proof the desired approximation guarantee we now approximate $d_\ell$ using a result obtained about tree metrics from \cite{approx}.}
     \label{fig:sum_over_capacities}
 \end{figure}
 
+To proof the desired approximation guarantee we now approximate $d_\ell$ using a result obtained about tree metrics 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}
+
+To be able to apply this result to our dual, we first need to show one more lemma.
+We need to rewrite the enumerator in \cref{eq:dual_compact} to not sum over tree edges but all edges in the graph.
+\begin{lemma}
+    Let $T$ be a spanning tree and $(V, M)$ a tree metric of $G = (V, E)$.
+    Then it holds that
+    \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}
+    See \cref{fig:sum_over_capacities}.
+\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}
+
 \section{Minimum Bisection}
 \label{sec:minimum_bisection}
 \blindtext