Mercurial > latex
view minimum_bisection/paper/term_paper.tex @ 149:4d5bf308e7ad
use ellipses of same size
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Sat, 05 Jul 2014 20:25:20 +0200 |
parents | 948ce3f9c3ad |
children | 8c10f9532afc |
line wrap: on
line source
\input{preamble.tex} \input{tikzpictures.tex} \title{Oblivious Routing and Minimum Bisection} \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} \institute{Technische Universit\"at M\"unchen\\ \email{markus.kaiser@in.tum.de}} \begin{document} \maketitle \thispagestyle{plain} \begin{abstract} I am an abstract! \end{abstract} \section{Oblivious Routing} \label{sec:oblivious_routing} \subsection{Problem definition} \label{sub:or_problem} \begin{figure}[tb] \centering \begin{tikzpicture}[flow graph] \path[use as bounding box] (-4, 2.4) rectangle (3.5,6.15); \flownodes \flowedges \draw (n) node[below=3] {\structure{u}} (j) node[below=3] {\structure{v}}; \begin{pgfonlayer}{demand} \draw[demand edge, bend left=20] (n) edge (j); \end{pgfonlayer} \begin{pgfonlayer}{marked} \draw[marked edge, tumgreen] (n.center) edge (l.center) (l.center) edge (h.center) (h.center) edge (i.center) (i.center) edge (j.center); \draw[marked edge, tumblue] (n.center) edge (m.center) (m.center) edge (e.center) (e.center) edge (c.center) (c.center) edge (k.center) (k.center) edge (j.center); \draw[marked edge, tumred] (n.center) edge (b.center) (b.center) edge (j.center); \end{pgfonlayer} \node at (-0.25, 2.4) {$\lambda_{green} = 0.25 \qquad \lambda_{blue} = 0.5 \qquad \lambda_{red} = 0.25$}; \end{tikzpicture} \caption{Oblivious Routing} \label{fig:oblivous_routing} \end{figure} \subsection{Formulation as a linear program} \label{sub:or_lp} \begin{figure}[tb] \centering \begin{tikzpicture}[flow graph] \flownodes \flowedges \flowtreeedges \begin{pgfonlayer}{background} \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=8pt] (el) {}; \end{pgfonlayer} \path (el) ++ (200:1) ++ (0, -0.5) coordinate (label); \node[below of = label] {\structure{$S(\alert{e_T})$}}; \begin{pgfonlayer}{marked} \foreach \source/ \dest in {l/h,m/e,m/f,n/b} \draw[tree edge, tumorange] (\source.center) edge (\dest.center); \end{pgfonlayer} \begin{pgfonlayer}{marked} \draw[tree edge, tumblue] (m.center) edge (e.center); \end{pgfonlayer} \path (m) -- node[flow capacity]{$e_T$} (e); \end{tikzpicture} \caption{Tree splits} \label{fig:tree_splits} \end{figure} \begin{figure}[tb] \centering \begin{tikzpicture}[flow graph] \flownodes \flowedges \draw (l) node[above=3] {\structure{u}} (i) node[above=3] {\structure{v}} (e) node[above left] {\structure{x}} (d) node[above=3] {\structure{z}} (c) node[below=3] {\structure{y}} ; \begin{pgfonlayer}{demand} \draw[demand edge, bend left=10] (l) edge (i); \end{pgfonlayer} \begin{pgfonlayer}{marked} \foreach \source/ \dest in {l/m,m/e,d/k,k/j,j/i} \draw[tree edge, tumgreen] (\source.center) edge (\dest.center); \end{pgfonlayer} \begin{pgfonlayer}{marked} \draw[tree edge, line width=4pt, white] (e.center) edge (d.center); \draw[tree edge, densely dashed, tumgreen!80] (e.center) edge (d.center); \foreach \source/\dest in {e/c,c/d} \draw[tree edge, tumblue!80] (\source.center) edge (\dest.center); \end{pgfonlayer} \begin{pgfonlayer}{marked} \foreach \source/ \dest in {l/h,h/i} \draw[tree edge, tumorange] (\source.center) edge (\dest.center); \end{pgfonlayer} \end{tikzpicture} \caption{Routing with Pathtrees} \label{fig:pathtrees} \end{figure} Primal \begin{alignat}{3} \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}} \label{eq:primal}\\ \st \quad && \sum_{i \in \Ih} \structure{\lambda_i} \sum_{\substack{e_T \in T_i: \\ \alert{(u, v)} \in P_i(e_T)}} C_i(e_T) & \leq \structure{\alpha} \alert{c_{uv}} & \qquad \forall \alert{u,v} \in V \\ && \sum_{i \in \Ih} \structure{\lambda_i} &= 1 \\ && \structure{\lambda} &\geq 0 \end{alignat} \subsection{Approximation guarantee using the dual} \label{sub:or_approx} Dual \begin{alignat}{3} \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ % \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\ && \structure{z} & \leq \sum_{e_T \in T_i} C_i(e_T) \sum_{(u,v) \in P_i(e_T)} \structure{\ell_{uv}} & \qquad \forall i \in \Ih \\ && \structure{\Ell} &\geq 0 \end{alignat} \begin{figure}[tb] \centering \begin{tikzpicture}[flow graph] \flownodes \flowedges \flowtreeedges \draw (n) node[above=3] {\structure{u}} (m) node[below=3] {a} (e) node[below=3] {b} (d) node[above=3] {c} (c) node[below=3] {d} (b) node[below=3] {\structure{v}}; \path (n) -- node[node on edge] {$c_{uv}$} (b); \begin{pgfonlayer}{marked} \draw[tree edge, tumorange] (n.center) edge (b.center); \end{pgfonlayer} \begin{pgfonlayer}{marked} \draw[tree edge, tumred] (m.center) edge (e.center); \end{pgfonlayer} \begin{pgfonlayer}{background} \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=8pt] (el) {}; \end{pgfonlayer} \end{tikzpicture} \caption{Sum over all Capacities} \label{fig:sum_over_capacities} \end{figure} \section{Minimum Bisection} \label{sec:minimum_bisection} \subsection{Problem definition} \label{sub:mb_problem} \begin{figure}[tb] \centering \begin{tikzpicture}[flow graph] \flownodes \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) {}; \end{pgfonlayer} \path (el) ++ (-30:2.6) node {\structure{$S$}}; \begin{pgfonlayer}{marked} \foreach \source/\dest in {b/j,f/c,f/e,m/e,l/h} \draw [tree edge, tumorange] (\source.center) -- (\dest.center); \end{pgfonlayer} \end{tikzpicture} \caption{Minimum Bisection} \label{fig:minimum_bisection} \end{figure} \subsection{Approximation using oblivious routing} \label{sub:mb_approx} \begin{figure}[tb] \begin{tikzpicture}[flow graph] \flownodes \flowedges \flowtreeedges \begin{pgfonlayer}{background} \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(c)(d)(g)(k)(j)(i)(e)(h), inner sep=3pt] (el) {}; \end{pgfonlayer} \path (el) ++ (-30:2.6) node {\structure{$S$}}; \draw (b) node[below=3] {\structure{u}} (j) node[below=3] {\structure{v}}; \begin{pgfonlayer}{marked} \foreach \source/\dest in {f/c,b/j,l/h} \draw [tree edge, tumblue, dash pattern=on 7pt off 7pt] (\source.center) -- (\dest.center); \foreach \source/\dest in {b/c,e/f,e/m} \draw [tree edge, tumred] (\source.center) -- (\dest.center); \end{pgfonlayer} \foreach \source/\dest/\name in {b/c/$e_3$,e/f/$e_2$,e/m/$e_1$} \path (\source) -- node[node on edge] {\name} (\dest); \end{tikzpicture} \caption{Costs are lower as tree costs} \label{fig:tree_bisections} \end{figure} \nocite{*} \bibliographystyle{alpha} \bibliography{term_paper} \end{document}