changeset 156:4ec3b7cbe311

abstract
author Markus Kaiser <markus.kaiser@in.tum.de>
date Wed, 30 Jul 2014 13:58:08 +0200
parents b7fd203d37d8
children 33290e7a43e4
files minimum_bisection/paper/term_paper.tex
diffstat 1 files changed, 4 insertions(+), 2 deletions(-) [+]
line wrap: on
line diff
--- 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.