# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1406723074 -7200
# Node ID 33290e7a43e4dce351870890173dfad2d1ddc579
# Parent  4ec3b7cbe311f7138dda57a27cdc139d439895aa
fix bisection picture

diff -r 4ec3b7cbe311 -r 33290e7a43e4 minimum_bisection/paper/term_paper.tex
--- a/minimum_bisection/paper/term_paper.tex	Wed Jul 30 13:58:08 2014 +0200
+++ b/minimum_bisection/paper/term_paper.tex	Wed Jul 30 14:24:34 2014 +0200
@@ -28,7 +28,7 @@
     It satisfies the following two properties:
     \begin{description}
         \item[Capacity Constraint:] For all $e \in E$, we have $f_e \leq c_e$.
-        \item[Flow Conservation:] For all $v \in V \setminus \left\{ s, t \right\}$, we have 
+        \item[Flow Conservation:] For all $v \in V \setminus \left\{ s, t \right\}$, we have
             \[\sum_{(u, v) \in E} f_{uv} = \sum_{(v, w) \in E} f_{vw}.\]
     \end{description}
     We denote $f_e \defeq f(e)$ for $e \in E$ and $f_{uv} \defeq f(u, v)$ for $u, v \in V$.
@@ -369,7 +369,7 @@
     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.
+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}
     The primal and dual linear program have a value of $\Oh(\log n)$.
@@ -395,20 +395,17 @@
 
 \section{Minimum Bisection}
 \label{sec:minimum_bisection}
-\blindtext
+
 
-\subsection{Problem definition}
-\label{sub:mb_problem}
 \begin{problem}[Minimum Bisection]
-    Given an undirected Graph $G = (V, E)$ and an edge-cost function $c : E \to \R^+$.
+    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}
 
-\blindtext
 
 \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 \R^+$ based on the tree splits induced by the edges of $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)\\
@@ -417,8 +414,6 @@
     The tree bisection of $T$ is an optimal solution of the minimum bisection problem with respect to the cost function $c_T$.
 \end{definition}
 
-\blindtext
-
 \begin{figure}[tb]
     \centering
     \begin{tikzpicture}[flow graph]
@@ -426,14 +421,14 @@
         \flowedges
 
         \begin{pgfonlayer}{background}
-            \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(c)(d)(g)(k)(j)(i)(e)(h), inner sep=3pt] (el) {};
+            \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(n)(l)(m)(h)(e)(f), rotate=10, inner sep=-8pt] (el) {};
         \end{pgfonlayer}
 
         \path (el)
-            ++ (-30:2.6) node {\structure{$S$}};
+            ++ (-120:2.1) node {\structure{$S$}};
 
         \begin{pgfonlayer}{marked}
-            \foreach \source/\dest in {b/j,f/c,f/e,m/e,l/h}
+            \foreach \source/\dest in {n/b,f/b,f/c,e/c,e/d,e/g,h/i}
             \draw [tree edge, tumorange] (\source.center) -- (\dest.center);
         \end{pgfonlayer}
     \end{tikzpicture}
@@ -441,12 +436,9 @@
     \label{fig:minimum_bisection}
 \end{figure}
 
-\subsection{Approximation using oblivious routing}
-\label{sub:mb_approx}
-
 \begin{algorithm}
     \label{alg:minimum_bisection}
-    Given graph $G = (V, E)$ and cost function $c : E \to \R^+$.
+    Given graph $G = (V, E)$ and cost function $c : E \to \Rnn$.
     \begin{enumerate}
         \item Interpret costs $c(e)$ as capacities
         \item Solve oblivious routing on $G$, obtaining trees $T_i$
@@ -462,11 +454,8 @@
     \end{align}
 \end{lemma}
 \begin{proof}
-    \blindtext
 \end{proof}
 
-\blindtext
-
 \begin{lemma}
     Let $\left\{ (T_i, \lambda_i) \mid i \in \Ih \right\}$ be a $\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.
@@ -494,7 +483,6 @@
     \cref{alg:minimum_bisection} is an $\Oh(\log n)$ approximation algorithm for the minimum bisection problem.
 \end{theorem}
 \begin{proof}
-    \blindtext
     \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^*)) \\