Mercurial > latex

changeset 148:948ce3f9c3ad

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add figures
author Markus Kaiser <markus.kaiser@in.tum.de>
date Sat, 05 Jul 2014 20:21:39 +0200
parents faff67582175
children 4d5bf308e7ad
files minimum_bisection/paper/preamble.tex minimum_bisection/paper/term_paper.tex minimum_bisection/paper/tikzpictures.tex
diffstat 3 files changed, 259 insertions(+), 13 deletions(-) [+]
line wrap: on
line diff
--- a/minimum_bisection/paper/preamble.tex	Sat Jul 05 18:35:18 2014 +0200
+++ b/minimum_bisection/paper/preamble.tex	Sat Jul 05 20:21:39 2014 +0200
@@ -5,6 +5,13 @@
 \usepackage[T1]{fontenc}
 \usepackage[utf8]{inputenc}
 
+\usepackage{amsmath}
+\usepackage{mathdots}
+\usepackage{mathtools}
+\mathtoolsset{showonlyrefs,showmanualtags}
+\usepackage{mathrsfs}
+\usepackage{csquotes}
+
 % \usepackage{xcolor}
 % \usepackage{tabu}
 \usepackage{tikz}
@@ -13,14 +20,8 @@
 \usetikzlibrary{shapes}
 \usetikzlibrary{fit}
 
-\usepackage{amsmath}
-\usepackage{mathdots}
-\usepackage{mathtools}
-\mathtoolsset{showonlyrefs,showmanualtags}
-\usepackage{mathrsfs}
-\usepackage{csquotes}
-
 \usepackage[pdftex]{hyperref}
+\usepackage[nameinlink, capitalize]{cleveref}
 
 \newcommand{\R}{\mathbb{R}}
 \newcommand{\Oh}{\mathcal{O}}
@@ -35,3 +36,16 @@
 \newcommand{\defeq}{\coloneqq} %Mathtools already defines this
 
 \DeclareMathOperator{\st}{s.t.}
+
+\pagestyle{plain}
+
+\xdefinecolor{tumblue}     {RGB}{  0,101,189}
+\xdefinecolor{tumgreen}    {RGB}{162,173,  0}
+\xdefinecolor{tumred}      {RGB}{229, 52, 24}
+\xdefinecolor{tumivory}    {RGB}{218,215,203}
+\xdefinecolor{tumorange}   {RGB}{227,114, 34}
+\xdefinecolor{tumlightblue}{RGB}{152,198,234}
+
+% Dummy commands to reuse beamer code
+\newcommand{\structure}[1]{#1}
+\newcommand{\alert}[1]{#1}
--- a/minimum_bisection/paper/term_paper.tex	Sat Jul 05 18:35:18 2014 +0200
+++ b/minimum_bisection/paper/term_paper.tex	Sat Jul 05 20:21:39 2014 +0200
@@ -9,12 +9,241 @@
 \begin{document}
 
 \maketitle
-
+\thispagestyle{plain}
 \begin{abstract}
-  Hier die Zusammenfassung eintragen
+  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=3pt] (el) {};
+        \end{pgfonlayer}
+
+        \path (el)
+            ++ (200:1.5)
+            ++ (0, 0) 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}
--- a/minimum_bisection/paper/tikzpictures.tex	Sat Jul 05 18:35:18 2014 +0200
+++ b/minimum_bisection/paper/tikzpictures.tex	Sat Jul 05 20:21:39 2014 +0200
@@ -4,15 +4,17 @@
 \pgfdeclarelayer{foreground}
 \pgfsetlayers{background,demand,marked,main,foreground}
 
+\tikzstyle{every node} = [font=\normalsize]
+
 \tikzstyle{edge} = [thick]
 \tikzstyle{marked edge} = [edge, line width=3pt, tumorange]
 \tikzstyle{directed} = [arrows={-latex}, shorten >=1pt]
 \tikzstyle{node on edge} = [fill=white, circle, inner sep=1pt, font=\footnotesize]
 
-\tikzstyle{flow graph} = [x=4em, y=4.5em]
+\tikzstyle{flow graph} = [x=4.5em, y=4em]
 \tikzstyle{flow node} = [circle, draw, thick, fill=tumblue!20, minimum size=6pt, inner sep=0pt]
 \tikzstyle{flow edge} = [edge]
-\tikzstyle{demand edge} = [edge, line width=2.5pt, arrows={-latex}, dotted, tumred!50]
+\tikzstyle{demand edge} = [edge, line width=4pt, arrows={-latex}, dash pattern= on 5pt off 3pt, tumred!50]
 \tikzstyle{tree edge} = [marked edge, tumgreen]
 \tikzstyle{flow capacity} = [node on edge]
 \tikzstyle{flow demand} = [node on edge, text=tumred]
@@ -76,7 +78,8 @@
             {e/g/1/0.7/left},
             {n/h/12/0.7/left},
             {k/m/5/0.8/right}}
-        \draw[demand edge, bend \bendage=15] (\source) edge node[flow demand, pos=\pos]{\demand} (\dest);
+        % \draw[demand edge, bend \bendage=15] (\source) edge node[flow demand, pos=\pos]{\demand} (\dest);
+        \draw[demand edge, bend \bendage=15] (\source) edge (\dest);
     \end{pgfonlayer}
 }
 \newcommand{\flowtreeedges}[1][]{%