# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1406720986 -7200
# Node ID b7fd203d37d8a5bc1fa2cfaf7d104e042a844295
# Parent  db04ec64fe7b141ef24718410c6c5c6dad8852d3
finish minimum bisection

diff -r db04ec64fe7b -r b7fd203d37d8 minimum_bisection/paper/term_paper.tex
--- a/minimum_bisection/paper/term_paper.tex	Tue Jul 29 18:50:12 2014 +0200
+++ b/minimum_bisection/paper/term_paper.tex	Wed Jul 30 13:49:46 2014 +0200
@@ -338,10 +338,7 @@
             \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=8pt] (el) {};
         \end{pgfonlayer}
     \end{tikzpicture}
-    \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}.}
+    \caption{The left hand side contains a product of capacity $c_{uv}$ and distance $M_{ab}$ iff $c_{uv}$ is part of the tree split introduced by the tree edge $(a, b)$. A capacity is part of a tree split iff $u$ and $v$ are not in the same connected component in the split. This is the case iff the tree edge lies on the path between $u$ and $v$. The sum of all tree edges between $u$ and $v$ is $M_{uv}$ by definition, yielding the right hand side of the sum.}
     \label{fig:sum_over_capacities}
 \end{figure}
 
@@ -370,20 +367,30 @@
     See \cref{fig:sum_over_capacities}.
 \end{proof}
 
+Combining all observations and lemmas now bounds the value of both linear programs logarithmically, directly following from the logaritmic bound of the tree metrics.
+
 \begin{lemma}
-    The linear program has a value of $\Oh(\log n)$.
+    The primal and dual linear program have a value of $\Oh(\log n)$.
 \end{lemma}
 \begin{proof}
-    For any $\Ell$ we know that for the \structure{minimizing tree $T_i$} holds
+    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.
     \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} \\
+        \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}
 \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 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.
+
 \section{Minimum Bisection}
 \label{sec:minimum_bisection}
 \blindtext