--- a/minimum_bisection/paper/term_paper.tex	Tue Jul 29 13:56:00 2014 +0200
+++ b/minimum_bisection/paper/term_paper.tex	Tue Jul 29 18:17:10 2014 +0200
@@ -167,7 +167,7 @@
 \end{lemma}
 
 We will use this observation to proof our approximation guarantee.
-Suppose we find a spanning tree such that every edge has capacity of the capacity of the corresponding tree split times some factor $\alpha \geq 1$.
+Suppose we find a spanning tree such that every edge has capacity of the capacity of the corresponding tree split divided by some factor $\alpha \geq 1$.
 \begin{align}
     \forall e_T \in E_T.\quad c_{e_T} &\geq \frac{1}{\alpha} C(e_T)
     \intertext{Using \cref{lem:optimal} we can bound the congestion of this spanning tree in relation to the optimal solution.}
@@ -178,35 +178,30 @@
 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.
+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$.
 
-Routing with Spanning Trees.
+For a given demand function, the demand $d_{uv}$ is routed through the unique $u$-$v$-paths in the trees $T_i$ according to the convex fractions.
+For every edge $e$ in the original graph we get
 \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}} \\
+    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}
 
-\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}
+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$.
+Instead of using the direct connections given by the tree edges to traverse the intermediate points, we are allowed to take any path in $G$.
+A pair of spanning tree and set of paths connecting two neighboured nodes in the tree is called a path tree.
 
 \begin{figure}[tb]
     \centering
@@ -238,16 +233,40 @@
             \draw[tree edge, tumblue!80] (\source.center) edge (\dest.center);
         \end{pgfonlayer}
 
-        \begin{pgfonlayer}{marked}
-            \foreach \source/ \dest in {l/h,h/i}
-            \draw[tree edge, tumorange] (\source.center) edge (\dest.center);
-        \end{pgfonlayer}
+        % \begin{pgfonlayer}{marked}
+        %     \foreach \source/ \dest in {l/h,h/i}
+        %     \draw[tree edge, tumorange] (\source.center) edge (\dest.center);
+        % \end{pgfonlayer}
     \end{tikzpicture}
-    \caption{Routing with Pathtrees}
+    \caption{A path tree is a pair of a spanning tree $T$ and a mapping $P$ from its edges to arbitrary paths in $G$. Instead of routing the demand $d_{uv}$ along the green tree edges, the edge $(x, z)$ is replaced by the blue edges $P((x, z)) = ((x, y), (y, z))$.}
     \label{fig:pathtrees}
 \end{figure}
 
-Primal
+\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$ identifying every edge $e_T = (x, y)$ of $T$ with a path in $G$ from $x$ to $y$.
+\end{definition}
+
+Note that the same edge in $G$ may well be used by multiple different paths in the same path tree.
+To now route any demand $d_{uv}$ using a path tree, we move along the unique $u$-$v$-path in the tree and stitch together the paths corresponding to the edges in the path.
+
+Since if routing with spanning tree $T_i$ the flow through every tree edge $e_T$ would be $D_i(T_i)$, the same amount of flow must now be added to every edge on the path $P_i(e_T)$.
+If we now consider a convex combination of path trees, the flow through every edge $e \in E$ is
+\begin{align}
+    f_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}
+
+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}.}
+    \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
+\end{align}
+
+We will now show that there always is a solution using path trees such that $\alpha \in \Oh(\log n)$ and sketch how to find such a set of trees.
+We denote the finite but exponentially sized set of all path trees over $G$ as $\Ih$.
+We can then formulate a linear program which enforces the assumption that every edge capacity is large enough and chooses a set of path trees such that $\alpha$ is minimal.
 \begin{alignat}{3}
     \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}} \label{eq:primal}\\
     \st \quad && \sum_{i \in \Ih} \structure{\lambda_i} \sum_{\substack{e_T \in T_i: \\ \alert{(u, v)} \in P_i(e_T)}} C_i(e_T) & \leq \structure{\alpha} \alert{c_{uv}} & \qquad \forall \alert{u,v} \in V \\
@@ -255,10 +274,13 @@
     && \structure{\lambda} &\geq 0
 \end{alignat}
 
+To gain an $\Oh(\log n)$ approximation algorithm from this linear program, we have to show that $\alpha$ is of at most logarithmic size and that it is possible to solve this linear program with exponentially sized sums in polynomial time, yielding a solution of polynomially many path trees.
+
 \subsection{Approximation guarantee using the dual}
 \label{sub:or_approx}
 
-Dual
+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.
 \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 \\
@@ -266,22 +288,30 @@
     && \structure{\Ell} &\geq 0
 \end{alignat}
 
-Rewrite \cref{eq:dual_constraints}
+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)$.
+
+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
 \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 \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.}
     \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
+Since we are only left with one constraint concerning $z$ and it is not otherwise needed in the dual program we can move it into the objective function and obtain a smaller LP.
+While it is no longer of exponential size, it might still take exponential time to find the minimum.
 \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
+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.
+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.
+If we drop the constraint enforcing $\beta = 1$, we have to divide the objective function by $\beta$.
+This yields a rather compact representation of the dual program.
 \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