# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1406721488 -7200
# Node ID 4ec3b7cbe311f7138dda57a27cdc139d439895aa
# Parent  b7fd203d37d8a5bc1fa2cfaf7d104e042a844295
abstract

diff -r b7fd203d37d8 -r 4ec3b7cbe311 minimum_bisection/paper/term_paper.tex
--- a/minimum_bisection/paper/term_paper.tex	Wed Jul 30 13:49:46 2014 +0200
+++ b/minimum_bisection/paper/term_paper.tex	Wed Jul 30 13:58:08 2014 +0200
@@ -11,7 +11,9 @@
 \maketitle
 \thispagestyle{plain}
 \begin{abstract}
-    \blindtext
+    Oblivious Routing is generalization of Multi Commodity Flows where the actual demand function is unknown.
+    This paper proofs the existence of an approximate solution using tree metrics which can easily be transformed into an $\Oh(\log n)$ approximation algorithm.
+    This result is then applied to the Minimum Bisection problem asking for an vertex bisection with minimal cost in the edges between the sets, also resulting in an $\Oh(\log n)$ approximation.
 \end{abstract}
 
 \section{Oblivious Routing}
@@ -34,7 +36,7 @@
 
 Maximum Flow problem can be solved in polynomial time using a number of algorithms, for example the Ford-Fulkerson method or Push-relabel algorithms, both of which are described in \cite{intro}.
 
-This paper will introduce a generalization of this problem known as \define{Oblivious Routing} and proof the existence of an $\Oh(\log n)$ approximation scheme based on \cite{racke2008optimal} and described in \cite{approx}.
+This paper will introduce a generalization of this problem known as \define{Oblivious Routing} and proof the existence of an $\Oh(\log n)$ approximation algorithm based on \cite{racke2008optimal} and described in \cite{approx}.
 After giving a definition of the problem, it is formulated as a linear problem and rewritten to yield the desired algorithm using a theorem giving an $\Oh(\log n)$ approximation of arbitrary metrics using tree metrics.
 Finally, the result is applied to give an $\Oh(\log n)$ approximation of the \define{Minimum Bisection} problem.