Mercurial > latex
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.