# HG changeset patch # User Markus Kaiser # Date 1406723279 -7200 # Node ID 79f47bbbaf87cc307a407127071a9094eeca6a6d # Parent 33290e7a43e4dce351870890173dfad2d1ddc579 no capital letters diff -r 33290e7a43e4 -r 79f47bbbaf87 minimum_bisection/paper/term_paper.tex --- a/minimum_bisection/paper/term_paper.tex Wed Jul 30 14:24:34 2014 +0200 +++ b/minimum_bisection/paper/term_paper.tex Wed Jul 30 14:27:59 2014 +0200 @@ -11,15 +11,15 @@ \maketitle \thispagestyle{plain} \begin{abstract} - Oblivious Routing is generalization of Multi Commodity Flows where the actual demand function is unknown. + 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. + 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} \label{sec:oblivious_routing} -\define{Maximum Flow} is a well understood algorithmic problem. +\define{Maximum flow} is a well understood algorithmic problem. Given a \define{directed graph $G = (V, E)$}, a mapping $c : E \to \Rnn$ denoted by $c_e \defeq c(e)$ assigning a maximum non-negative capacity to every edge and a \define{source} and \define{target} node $s, t \in V$, we are asked to find a flow of maximum value from $s$ to $t$. For simplicity, we assume that $G$ is complete, which can be achieved by adding edges of capacity $0$. @@ -34,11 +34,11 @@ We denote $f_e \defeq f(e)$ for $e \in E$ and $f_{uv} \defeq f(u, v)$ for $u, v \in V$. \end{definition} -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}. +The 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 algorithm 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. +Finally, the result is applied to give an $\Oh(\log n)$ approximation of the \define{minimum bisection} problem. \subsection{Problem definition} \label{sub:or_problem} @@ -79,11 +79,11 @@ \node at (-0.25, 2.4) {$\lambda_{green} = 0.25 \qquad \lambda_{blue} = 0.5 \qquad \lambda_{red} = 0.25$}; \end{tikzpicture} - \caption{A solution to the oblivious flow problem gives a set of paths and an associated convex combination for any two nodes $u, v \in V$. In this case, we are given the green, blue and red path from $u$ to $v$. The dashed demand $d_{uv}$ gets routed along these three paths, split according to the factors $\lambda_i$.} + \caption{A solution to the oblivious routing problem gives a set of paths and an associated convex combination for any two nodes $u, v \in V$. In this case, we are given the green, blue and red path from $u$ to $v$. The dashed demand $d_{uv}$ gets routed along these three paths, split according to the factors $\lambda_i$.} \label{fig:oblivous_routing} \end{figure} -To define Oblivious Routing, we first consider a simpler generalization of Maximum Flow, the \define{Multi-Commodity Flow} problem. +To define oblivious routing, we first consider a simpler generalization of maximum flow, the \define{multi-commodity flow} problem. Instead of a single source and target node, we now allow and arbitrary number of nonnegative flow demands between two nodes given by a \define{demand function $d : V^2 \to \Rnn$} on a now undirected graph. Every such demand $d(u, v)$ must be routed from $u$ to $v$ using a set of $u$-$v$-paths and the total flow $f_e$ on an edge $e \in E$ is the sum of all demands routed through it. The task of is now to find a flow satisfying all demands while exceeding the capacities of all edges as little as possible. @@ -396,6 +396,7 @@ \section{Minimum Bisection} \label{sec:minimum_bisection} +The knowledge about the existence of an $\Oh(\log n)$ approximation algorithm for the oblivious routing problem \begin{problem}[Minimum Bisection] Given an undirected Graph $G = (V, E)$ and an edge-cost function $c : E \to \Rnn$. @@ -522,9 +523,7 @@ \label{fig:tree_bisections} \end{figure} - \nocite{*} \bibliographystyle{alpha} \bibliography{term_paper} - \end{document}