Mercurial > latex
changeset 145:46887cff614e
move presentation into subfolder
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Sat, 05 Jul 2014 17:27:53 +0200 |
| parents | 9fde0cffa295 |
| children | 1d9a7448a284 |
| files | minimum_bisection/beamerthemeLEA2.sty minimum_bisection/preamble.tex minimum_bisection/presentation.pdf minimum_bisection/presentation.tex minimum_bisection/presentation/beamerthemeLEA2.sty minimum_bisection/presentation/preamble.tex minimum_bisection/presentation/presentation.pdf minimum_bisection/presentation/presentation.tex minimum_bisection/presentation/tikzpictures.tex minimum_bisection/presentation/tum.pdf minimum_bisection/tikzpictures.tex |
| diffstat | 11 files changed, 1314 insertions(+), 1230 deletions(-) [+] |
line wrap: on
line diff
--- a/minimum_bisection/beamerthemeLEA2.sty Thu Jun 12 13:45:56 2014 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,61 +0,0 @@ -\ProvidesPackage{beamerthemeLEA2} - -\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} - -%% shadow, font, color, outer, inner -%% normal text, alerted text, example text, structure - -\useoutertheme{split} - -\setbeamercolor{normal text}{fg=black,bg=white} -\setbeamercolor{alerted text}{fg=tumred,bg=white} -\setbeamercolor{example text}{fg=tumgreen,bg=white} -\setbeamercolor{structure}{fg=tumblue,bg=white} -\setbeamercolor{titlelike}{fg=tumblue} -\setbeamercolor{subtitle}{fg=black} -\setbeamerfont{title}{series=\bfseries} - -\setbeamertemplate{sections/subsections in toc}[square] -\setbeamertemplate{items}[square] -\setbeamertemplate{navigation symbols}[only frame symbol] - -\setbeamertemplate{blocks}[default] - -\setbeamercolor{block title} {use=normal text, fg=black,bg=tumlightblue} -\setbeamercolor{block title alerted}{use=alerted text,fg=white,bg=alerted text.fg} -\setbeamercolor{block title example}{use=example text,fg=white,bg=example text.fg} - -\setbeamercolor{block body} {parent=normal text,use=block title, bg=block title.bg!25!bg} -\setbeamercolor{block body alerted}{parent=normal text,use=block title alerted,bg=block title.bg!25!bg} -\setbeamercolor{block body example}{parent=normal text,use=block title example,bg=block title example.bg!15!bg} - -%\pgfdeclareimage[height=5mm]{uni}{TU_Muenchen_Logo_Breit} -\pgfdeclareimage[height=5mm]{uni}{tum} -\logo{\pgfuseimage{uni}} - -\defbeamertemplate*{footline}{infolines theme}{% - \hspace*{2ex}\raisebox{1.5ex}[-1.5ex]{% - \tiny\insertframenumber{}/\inserttotalframenumber \hspace{5mm} \insertnavigation{0.8\paperwidth}}% -} - -\setbeamertemplate{frametitle}{ - \begin{beamercolorbox}[wd=\textwidth,leftskip=0mm]{frametitle} - \usebeamerfont*{frametitle} - \insertframetitle\hfill\parbox{10mm}{\vspace{-1.5mm}\insertlogo} - \end{beamercolorbox} - \vspace{-2.5mm}\textcolor{tumblue}{\noindent\rule{\textwidth}{0.4px}} -} -% hier kein Logo -\setbeamertemplate{sidebar right}{}%{\vfill\vskip2pt\llap{\usebeamertemplate***{navigation symbols}\hskip1mm}\vskip2pt} - -\setbeamertemplate{headline}{} - -\setbeamercovered{transparent} - -% escapeinside= removed for utf8 compatibility -\lstset{numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\small, backgroundcolor=\color{tumlightblue}}
--- a/minimum_bisection/preamble.tex Thu Jun 12 13:45:56 2014 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,54 +0,0 @@ -\documentclass[compress, 9pt, german, t]{beamer} -\usepackage{etex} - -\usepackage[english]{babel} -\uselanguage{English} -\languagepath{English} - -\usepackage[T1]{fontenc} -\usepackage[utf8]{inputenc} - -\usepackage{arev} -\usepackage{mathpazo} -\usepackage{microtype} - -\usepackage{url} -\usepackage{listings} -\usepackage{xcolor} -\usepackage{tabu} -\usepackage{tikz} -\usepackage{pgfplots} -\pgfplotsset{compat=1.9} -\usetikzlibrary{shapes} -\usetikzlibrary{fit} - -\usepackage{amsmath} -\usepackage{mathdots} -\usepackage{mathtools} -\mathtoolsset{showonlyrefs,showmanualtags} -\usepackage{mathrsfs} -\usepackage{csquotes} - -\usepackage{todonotes} - -\usepackage{beamerthemeLEA2} -\setbeamercovered{transparent} - -\newcommand{\N}{\mathbb{N}} -\newcommand{\Z}{\mathbb{Z}} -\newcommand{\Q}{\mathbb{Q}} -\newcommand{\R}{\mathbb{R}} -\newcommand{\C}{\mathbb{C}} -\newcommand{\Prob}{\mathrm{P}} -\newcommand{\Oh}{\mathcal{O}} -\newcommand{\Ih}{\mathcal{I}} -\newcommand{\Ell}{\mathcal{L}} - -\newcommand{\abs}[1]{\left\vert #1 \right\vert} -\newcommand{\powerset}[1]{\mathcal{P}\left( #1 \right)} -\newcommand{\setnot}[1]{\overline{#1}} -\newcommand{\setsymdiff}{\,\triangle\,} - -\newcommand{\defeq}{\coloneqq} %Mathtools already defines this - -\DeclareMathOperator{\st}{s.t.}
--- a/minimum_bisection/presentation.tex Thu Jun 12 13:45:56 2014 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1014 +0,0 @@ -\input{preamble.tex} -\input{tikzpictures.tex} - -\title{Oblivious Routing and Minimum Bisection} -\subtitle{Seminar: Approximation Algorithms} -\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} -\date{June 3, 2014} - -\begin{document} -\begin{frame} - \titlepage -\end{frame} - -\begin{frame} - \frametitle{Flow Problems} - \begin{problem}[Single Commodity Flow] - Given - \begin{itemize}[<+->] - \item An (un)directed Graph $G = (V, E)$ - \item A \structure{capacity function} $c : E \to \R^+$ - \item A source $s$ and a target $t$ - \end{itemize} - \uncover<4->{Calculate a maximum possible \structure{flow} $f : E \to \R^+$ through $G$.} - \end{problem} - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges[directed] - \only<2->{\flowcapacities} - - \draw<3-> - (n.south) node[below] {\structure{s}} - (j.south) node[below] {\structure{t}}; - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Flow Problems} - - \begin{problem}[Multi Commodity Flow] - Given - \begin{itemize} - \item An undirected Graph $G = (V, E)$ - \item A capacity function $c : E \to \R^+$ - \item<2-> A \structure{demand function} $d : V^2 \to \R^+$ - \end{itemize} - \uncover<3->{Calculate a flow $f$ with least \structure{congestion $\rho = \max_{e \in E}\frac{f_e}{c_e}$}.} - \end{problem} - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - \flowcapacities - \only<2->{\flowdemands} - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Oblivious Routing} - - \begin{problem}[Oblivious Routing] - Given - \begin{itemize} - \item An undirected Graph $G = (V, E)$ - \item A capacity function $c : E \to \R^+$ - \end{itemize} - Calculate a combination of paths for each $(u, v) \in V^2$ such that for \alert{any} demand function the \structure{congestion} will be as small as possible. - \end{problem} - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - \flowcapacities - - \draw<2-> - (n.south) node[below] {\structure{u}} - (j.south) node[below] {\structure{v}}; - - \only<3-> { - \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} - - \path[font=\Large] - (n) - +(-0.5, 0.5) node[tumgreen] {$\frac{1}{4}$} - +(-0.5, 0) node[tumblue] {$\frac{1}{2}$} - +(-0.5, -0.5) node[tumred] {$\frac{1}{4}$}; - } - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Routing with a Spanning Tree} - - \begin{itemize} - \item Choose any \structure{spanning tree $T$} of $G$ - \item Routing along its unique paths is a feasible solution - \end{itemize} - - \vfill - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - \flowtreeedges - - \only<2-> { - \draw - (l) node[above right] {\structure{u}} - (i) node[above right] {\structure{v}}; - \begin{pgfonlayer}{demand} - \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i); - \end{pgfonlayer} - } - - \only<3-> { - \begin{pgfonlayer}{marked} - \foreach \source/ \dest in {l/m,m/e,e/d,d/k,k/j,j/i} - \draw[tree edge, tumred] (\source.center) edge (\dest.center); - \end{pgfonlayer} - } - - \only<4-> { - \flowcapacities - \node[below=0 of b] {\structure{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{10}{2} = 5$}}; - } - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Tree Splits} - - \begin{itemize} - \item Removing one edge $e_T$ from a ST creates a \structure{node partition $S(e_T)$} - \item Every such partition has a \structure{capacity $C(e_T)$} - \item And a \structure{demand $D(e_T)$} - \end{itemize} - \begin{align} - C(e_T) &= \sum_{\substack{u \in S(e_T), \\ v \not\in S(e_T)}} c_{uv} & - D(e_T) &= \sum_{\substack{u \in S(e_T), \\ v \not\in S(e_T)}} c_{uv} - \end{align} - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - \flowtreeedges - - \only<2-> { - \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=3pt] (el) {}; - \end{pgfonlayer} - - \path (el) - ++ (200:1.5) - ++ (0, -0.5) coordinate (label); - \node[below=0 of label] {\structure{$S(\alert{e_T})$}}; - } - - \only<3> { - \flowcapacities - - \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} - } - - \only<3-> { - \node[below=0.5 of label] {$C(e_T) = 10$}; - } - - \only<4-> { - \flowdemands - - \begin{pgfonlayer}{demand} - \foreach \source/\dest/\demand/\pos/\bendage in { - {n/j/10/0.2/right}, - {n/h/12/0.7/left}, - {k/m/5/0.8/right}} - \draw[demand edge, bend \bendage=15, tumorange] (\source) edge node[flow demand, text=tumorange, pos=\pos]{\demand} (\dest); - \end{pgfonlayer} - - \node[below=1 of label] {$D(e_T) = 27$}; - } - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Optimal Solution} - - \begin{lemma} - For any tree $T$ and any tree edge $e_T$, we know that for \alert{any routing} in $G$ there must be an edge with \structure{congestion} - \begin{align} - \rho_e \geq \frac{D(e_T)}{C(e_T)} - \end{align} - And therefore the \structure{optimal solution $\rho^\ast$} can be no better. - \end{lemma} - - \vfill - \pause - - \begin{itemize} - \item Suppose we find a tree such that for some $\alpha$ - \begin{align} - \forall e_T \in E_T.\quad c_{e_T} \geq \frac{1}{\alpha} C(e_T) - \end{align} - \item Then we have - \begin{align} - \structure{\rho_T} = \max_{e_T} \frac{D(e_T)}{c_{e_T}} \structure{\leq} \alpha \max_{e_T} \frac{D(e_T)}{C(e_T)} \leq \structure{\alpha \rho^\ast} - \end{align} - \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{Routing with multiple Spanning Trees} - - \begin{itemize} - \item Choose a \structure{set of spanning trees $\left\{ T_i \right\}$} of $G$ - \item And a \structure{convex combination $\lambda$} with $\sum_i \lambda_i = 1$, $\lambda \geq 0$ - \item Routing is now split according to this combination. For $e \in E$ - \begin{align} - f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e) - \end{align} - \end{itemize} - - \vfill - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - - \draw - (l) node[above right] {\structure{u}} - (i) node[above right] {\structure{v}}; - - \path - (n) - ++ (-1, -0.5) coordinate (label); - - \only<2> { - \flowtreeedges - } - - \only<2-> { - \node[tumgreen, below=0 of label, anchor=west] {$\displaystyle\lambda_1 = \frac{1}{2}$}; - } - - \only<3> { - \flowtreeedgestwo[tumorange] - } - - \only<3-> { - \node[tumorange, below=0.5 of label, anchor=west] {$\displaystyle\lambda_2 = \frac{1}{2}$}; - } - - \only<4-> { - \begin{pgfonlayer}{demand} - \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i); - \end{pgfonlayer} - - \begin{pgfonlayer}{marked} - \foreach \source/ \dest in {l/m,m/e,e/d,d/k,k/j,j/i} - \draw[tree edge, tumgreen] (\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} - } - - \only<5-> { - \flowcapacities - \node[below=1 of label, anchor=west] {\structure{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{5}{2} = 2.5$}}; - } - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Routing with multiple Spanning Trees} - - \begin{itemize} - % \item Remember that the total flow on edge $e \in E$ is - % \begin{align} - % f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e) - % \end{align} - \item Suppose we now find a \structure{set of trees} such that for some $\alpha$ - \begin{align} - \forall e \in E.\quad c_{e} \geq \frac{1}{\alpha} \sum_{\substack{i:\\e \in T_i}} \lambda_i C_i(e) - \end{align} - \vfill - \item Then we have - \begingroup - \addtolength{\jot}{.5em} - \begin{align} - \structure{\rho} &= \hphantom{\alpha}\max_{e} \frac{f(e)}{c_{e}} \\ - &= \hphantom{\alpha}\max_{e} \frac{\sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)}{c_e} \\ - &\structure{\leq} \alpha \max_{e} \frac{\sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)}{\sum_{\substack{i:\\e \in T_i}} \lambda_i C_i(e)} \\ - &\leq \alpha \max_{e} \max_{i} \frac{D_i(e)}{C_i(e)} \leq \structure{\alpha \rho^\ast} - \end{align} - \endgroup - \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{Pathtrees} - - \begin{itemize} - \item Identify every edge in a tree with a \structure{path} in $G$ - \item These paths can \structure{overlap} - \item For tree $T$ we get a mapping $P_T : E_T \to E^+$ - \end{itemize} - - \vfill - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - \flowtreeedges - \flowcapacities - - \draw - (e) node[above right] {\structure{a}} - (d) node[above=0.1] {\structure{b}}; - - \only<2-> { - \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} - } - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Routing with multiple Pathtrees} - - \begin{itemize} - \item Choose a \structure{set of pathtrees $\left\{ T_i \right\}$} of $G$ with \structure{combination $\lambda$} - \item Now route along the paths identified with edges. For $e \in E$ - \begin{align} - f(\structure{e}) &= \sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(\alert{e_T})}} D_i(\alert{e_T}) - \end{align} - \end{itemize} - - \vfill - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - - \draw - (l) node[above right] {\structure{u}} - (i) node[above right] {\structure{v}}; - - \path - (n) - ++ (-1, -0.5) coordinate (label); - - \only<2> { - \flowtreeedges - } - - \only<2-> { - \node[tumgreen, below=0 of label, anchor=west] {$\displaystyle\lambda_1 = \frac{2}{3}$}; - } - - \only<3> { - \flowtreeedgestwo[tumorange] - } - - \only<3-> { - \node[tumorange, below=0.5 of label, anchor=west] {$\displaystyle\lambda_2 = \frac{1}{3}$}; - } - - \only<4-> { - \begin{pgfonlayer}{demand} - \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{9} (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} - } - - \only<5-> { - \flowcapacities - \node[below=1 of label, anchor=west] {\structure{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{6}{4} = 2$}}; - } - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Routing with multiple pathtrees} - - \begin{itemize} - \item Again suppose we now find a \structure{set of trees} such that for some $\alpha$ - \begin{align} - \forall \structure{e} \in E.\quad c_{e} \geq \frac{1}{\alpha} \sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(\alert{e_T})}} C_i(\alert{e_T}) - \end{align} - \item Then we have - \begingroup - \addtolength{\jot}{.5em} - \begin{align} - \rho &= \hphantom{\alpha}\max_{\structure{e}} \frac{f(\structure{e})}{c_{\structure{e}}} \\ - &\leq \alpha \max_{\structure{e}} \frac{\sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(e_T)}} D_i(\alert{e_T})}{\sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(e_T)}} C_i(\alert{e_T})} \\ - &\leq \alpha \max_{\structure{e}} \max_{i} \frac{D_i(\structure{e})}{C_i(\structure{e})} \leq \alpha \rho^\ast - \end{align} - \endgroup - \end{itemize} - - \vfill - - \only<2> { - \begin{center} - How do we find such a set of trees? How large is $\alpha$? - \end{center} - } -\end{frame} - -\begin{frame} - \frametitle{Primal program} - - \begin{block}{Primal Program} - Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.\\ - We want to find the best trees with smallest $\alpha$. - \begin{alignat}{3} - \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\ - \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} - \end{block} - - \vfill - - \begin{center} - We want to show that $\alpha \in \Oh(\log n)$ - \end{center} -\end{frame} - -\begin{frame} - \frametitle{Dual Program} - - \begin{block}{Dual Program} - Let $\Ih$ be the exponentially large set of \structure{all pathtrees}. - \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} - \end{block} - - \vfill - - \begin{center} - If $z \in \Oh(\log n)$ then $\alpha \in \Oh(\log n)$ by strong duality - \end{center} -\end{frame} - -\begin{frame} - \frametitle{Solution of the Dual Program} - - \begin{block}{Dual Program} - Let $\Ih$ be the exponentially large set of \structure{all pathtrees}. - \begin{alignat}{3} - \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ % - \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\ - \only<-2>{ - && \structure{z} & \leq \sum_{e_T \in T_i} C_i(e_T) \tikzmark{a}\sum_{(u,v) \in P_i(e_T)} \structure{\ell_{uv}} \tikzmark{b} & \qquad \forall i \in \Ih \\ - } - \only<3-4>{ - && \structure{z} & \leq \tikzmark{c}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)\tikzmark{d} & \qquad \forall i \in \Ih \\ - } - \only<5->{ - && \structure{z} & \leq \min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)\\ - } - && \structure{\Ell} &\geq 0 - \end{alignat} - \end{block} - - \vfill - - \begin{itemize} - \item We interpret the $\structure{\ell_{uv}}$ as edge lengths in $G$ - \item They define a \structure{shortest path metric $d_{\structure{\ell}}(u, v)$} - \item For an edge $e = (x, y)$ we write $d_{\structure{\ell}}(e) \defeq d_{\structure{\ell}}(x, y)$ - \end{itemize} - \begin{tikzpicture}[remember picture, overlay] - \only<2> {% - \node[fit=(a)(b), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below:{$\geq d_{\structure{\ell}}(e_T)$}}] {}; - } - \only<4> {% - \node[fit=(c)(d), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below right:{$\geq \min_{i \in \Ih} \cdots$}}] {}; - } - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Solution of the Dual Program} - - \begin{block}{Dual Program} - Let $\Ih$ be the exponentially large set of \structure{all pathtrees}. - \only<1-2>{% - \begin{alignat}{3} - \max_{\structure{\Ell}} \quad & \mathrlap{\min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)}\\ - \st \quad && \tikzmark{a}\sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1\tikzmark{b} \\ - && \structure{\Ell} &\geq 0 - \end{alignat} - \vspace{-1em} - } - \only<3>{% - \begin{alignat}{3} - \max_{\structure{\Ell}} \quad & \min_{i \in \Ih}\frac{\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)}{\sum_{u, v \in V} c_{uv} \structure{\ell_{uv}}}\\ - \st \quad & \structure{\Ell} \geq 0 - \end{alignat} - } - \end{block} - - \vfill - - \uncover<2-3>{ - \begin{itemize} - \item Now suppose - \begin{align} - \sum_{u, v \in V} c_{uv} \ell_{uv} = \beta > 0 - \end{align} - \item If we scale every length by $\frac{1}{\beta}$ our solution will change by $\frac{1}{\beta}$ - \end{itemize} - } - \begin{tikzpicture}[remember picture, overlay] - \only<2>{ - \node[fit=(a)(b), highlight, minimum height=2.5em, inner sep=-3pt] {}; - } - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Tree Metric} - - \begin{theorem}[Tree Metric] - For our metric $d_\ell$ there exists a \structure{tree metric $(V, M)$} with - \begingroup - \addtolength{\jot}{.5em} - \begin{alignat}{2} - d_\ell(u, v) &\leq M_{uv} & \forall u, v \in V\\ - \sum_{u, v \in V} c_{uv} M_{uv} &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v) - \end{alignat} - \endgroup - \end{theorem} - - \vfill - - \centering - \begin{tikzpicture}[grow=down, level distance = 25] - \begin{scope} - \tikzstyle{every node} = [draw, flow node] - \tikzstyle{edge from parent} = [draw, edge] - - \tikzstyle{level 1} = [sibling distance = 100] - \tikzstyle{level 2} = [sibling distance = 50] - \tikzstyle{level 3} = [sibling distance = 30] - \node[label=above:$z$] (z) {} - child { - node[label=above left:$y$] (y) {} - edge from parent - child { - node[label=above left:$x$] (x) {} - edge from parent - child { - node[label=below left:$\structure{u}$] (u) {} - edge from parent - } - child { - node {} - edge from parent - } - } - child { - node {} - edge from parent - child { - node {} - edge from parent - } - child { - node {} - edge from parent - } - } - } - child { - node[label=above right:$\structure{v}$] (v) {} - edge from parent - child { - node {} - edge from parent - child { - node {} - edge from parent - } - child { - node {} - edge from parent - } - } - child { - node {} - edge from parent - child { - node {} - edge from parent - } - child { - node {} - edge from parent - } - } - }; - \end{scope} - - \begin{pgfonlayer}{marked} - \foreach \source/\dest in {u/x,x/y,y/z,z/v} - \draw [tree edge, tumred] (\source.center) -- (\dest.center); - \end{pgfonlayer} - - \node at (0, -3.5) {$M_{uv} = M_{ux} + M_{xy} + M_{yz} + M_{zv}$}; - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Sum over all capacities} - - \begin{lemma}[] - Let $T$ be a spanning tree and $(V, M)$ a tree metric of $G = (V, E)$. Then - \begin{align} - \sum_{(x, y) \in E_T} C(x, y) M_{xy} = \sum_{(u, v) \in E} c_{uv} M_{uv} - \end{align} - \end{lemma} - - \vfill - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - \flowtreeedges - - \draw - (n) node[above=0.1] {\structure{u}} - (m) node[below=0.05] {a} - (e) node[below=0.05] {b} - (d) node[above=0.1] {c} - (c) node[below=0.05] {d} - (b) node[above=0.1] {\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} - - \only<2> { - \begin{pgfonlayer}{marked} - \draw[tree edge, tumred] (n.center) edge (m.center); - \end{pgfonlayer} - - \begin{pgfonlayer}{background} - \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(n), inner sep=15pt] (el) {}; - \end{pgfonlayer} - } - \only<3> { - \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=3pt] (el) {}; - \end{pgfonlayer} - } - \only<4> { - \begin{pgfonlayer}{marked} - \draw[tree edge, tumred] (e.center) edge (d.center); - \end{pgfonlayer} - - \begin{pgfonlayer}{background} - \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m)(e)(f), inner sep=3pt] (el) {}; - \end{pgfonlayer} - } - \only<5> { - \begin{pgfonlayer}{marked} - \draw[tree edge, tumred] (d.center) edge (c.center); - \end{pgfonlayer} - - \begin{pgfonlayer}{background} - \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=-10, fit=(c)(b), inner sep=3pt] (el) {}; - \end{pgfonlayer} - } - \only<6> { - \begin{pgfonlayer}{marked} - \draw[tree edge, tumred] (c.center) edge (b.center); - \end{pgfonlayer} - - \begin{pgfonlayer}{background} - \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(b), inner sep=15pt] (el) {}; - \end{pgfonlayer} - } - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Value of the Dual Problem} - - \begin{block}{Dual Program} - Let $\Ih$ be the exponentially large set of \structure{all pathtrees}. - \begin{alignat}{3} - \max_{\structure{\Ell}} \quad & \min_{i \in \Ih}\frac{\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)}{\sum_{u, v \in V} c_{uv} \structure{\ell_{uv}}}\\ - \st \quad & \structure{\Ell} \geq 0 - \end{alignat} - \end{block} - - For any $\Ell$ we know that for the \structure{minimizing tree $T_i$} holds - \begin{align} - \sum_{e_T \in T_i} C_i(e_T) d_\ell(e_T) &\leq \sum_{e_T \in T_i} C_i(e_T) M_{e_T} \\ - &= \sum_{u, v \in V} c_{uv} M_{uv} \\ - &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v) \\ - &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} \ell_{uv} \\ - \frac{\sum_{e_T \in T_i} C_i(e_T) d_\ell(e_T)}{\sum_{u, v \in V} c_{uv} \ell_{uv}} &\leq \Oh(\log n) - \end{align} -\end{frame} - -\begin{frame} - \frametitle{Value of the Primal Program} - - \begin{block}{Primal Program} - Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.\\ - We want to find the best trees with smallest $\alpha$. - \begin{alignat}{3} - \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\ - \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} - \end{block} - - \vfill - - \begin{itemize} - \item There is a $\structure{\lambda}$ such that $\structure{\alpha \in \Oh(\log n)}$ - \item But why are polynomially many trees enough? - \item This gives an \alert{$\Oh(\log n)$-approximation} - \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{Minimum Bisection} - - \begin{problem}[Minimum Bisection] - Given - \begin{itemize} - \item An undirected Graph $G = (V, E)$ - \item A cost function $c : E \to \R^+$ - \end{itemize} - Find a set $S \subset V$ containing half the vertices with \structure{minimal split cost}. - \end{problem} - - \vfill - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - \flowcapacities - - \only<2-> { - \begin{pgfonlayer}{background} - \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {}; - \end{pgfonlayer} - - \path (el) - ++ (-30:2.3) node {\structure{$S$}}; - } - - \only<3-4> { - \begin{pgfonlayer}{marked} - \foreach \source/\dest in {b/j,b/c,c/f,e/c,e/d,e/g,h/i} - \draw [tree edge, tumorange] (\source.center) -- (\dest.center); - \end{pgfonlayer} - - \path (n) - ++ (-0.5, -1.5) node[tumorange, anchor=west] {\alt<3>{$\hphantom{c(}\delta(S)$}{$c(\delta(S)) = 25$}}; - } - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Approximation Algorithm} - - \begin{block}{Minimum Bisection Approximation} - Given graph $G = (V, E)$ and cost function $c : E \to \R^+$. - \begin{enumerate} - \item Interpret costs $c(e)$ as \structure{capacities} - \item Solve oblivious routing on $G$, obtaining \structure{trees $T_i$} - \item Find minimum \structure{tree bisections $X_i$} for all trees $T_i$ - \item Choose the $X_i$ with \structure{lowest $c(\delta(X_i))$} - \end{enumerate} - \end{block} - - \vfill - \pause - - We have to show - \begin{itemize} - \item What the $X_i$ actually are - \item An \alert{$\Oh(\log n)$-approximation} guarantee - \item That we can find the $X_i$ in polynomial time - \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{Tree Bisections} - - \begin{itemize} - \item Given a spanning tree $T$ of $G$ with an edge $e_T \in E_T$ - \item Define a new \structure{cost function $c_T$} using tree splits - \end{itemize} - \begin{align} - c_T(e_T) &= C(e_T) & c_T(\delta(S)) = \sum_{\substack{e_T \in E_T:\\e_T \in \delta(S)}} C(e_T) - \end{align} - - \vfill - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - \flowtreeedges - - \only<2-> { - \begin{pgfonlayer}{background} - \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {}; - \end{pgfonlayer} - - \path (el) - ++ (-30:2.3) node {\structure{$S$}}; - } - - \only<3> { - \begin{pgfonlayer}{marked} - \foreach \source/\dest in {b/c,e/d,h/i} - \draw [tree edge, tumred] (\source.center) -- (\dest.center); - \end{pgfonlayer} - - \foreach \source/\dest/\name in {b/c/$e_3$,e/d/$e_2$,h/i/$e_1$} - \path (\source) -- node[node on edge] {\name} (\dest); - - \path (n) - ++ (-1, -1.5) node[tumred, anchor=west] {$\displaystyle c_T(\delta(S)) = \sum_{k=1}^3 C(e_k)$}; - } - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Tree Bisections} - - \begin{lemma}[] - For any spanning tree $T$ and any $S \subseteq V$ we have - \begin{align} - c(\delta(S)) \leq c_T(\delta(S)) - \end{align} - \end{lemma} - - \vfill - - \centering - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - \flowtreeedges - - \begin{pgfonlayer}{background} - \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {}; - \end{pgfonlayer} - - \path (el) - ++ (-30:2.3) node {\structure{$S$}}; - - \draw - (b) node[below=0.05] {\structure{u}} - (j) node[below=0.05] {\structure{v}}; - - \begin{pgfonlayer}{marked} - \foreach \source/\dest in {b/j,f/c,e/c,e/g} - \draw [tree edge, tumblue, dash pattern=on 7pt off 7pt] (\source.center) -- (\dest.center); - - \foreach \source/\dest in {b/c,e/d,h/i} - \draw [tree edge, tumred] (\source.center) -- (\dest.center); - \end{pgfonlayer} - - \foreach \source/\dest/\name in {b/c/$e_3$,e/d/$e_2$,h/i/$e_1$} - \path (\source) -- node[node on edge] {\name} (\dest); - \end{tikzpicture} -\end{frame} - -\begin{frame} - \frametitle{Tree Bisections} - - \begin{lemma}[] - Let $\left\{ T_i \right\}$ be a solution to the \structure{oblivious flow} problem on $G$.\\ - Then for any $S \subseteq V$ we have - \begin{align} - \sum_i \lambda_i c_{T_i}(\delta(S)) \leq \Oh(\log n) c(\delta(S)) - \end{align} - \end{lemma} - - \vfill - - \begin{itemize} - \only<1> { - \item Remember from the primal program that \structure{for all $u, v \in V$} - \begin{align} - \sum_i \lambda_i \sum_{\substack{e_T \in T_i:\\\structure{(u,v)} \in P_i(e_T)}} C_i(e_T) \leq \Oh(\log n) \structure{c_{uv}} - \end{align} - \item We sum up the inequalities for all $(u, v) \in \delta(S)$ - } - \only<2> { - \item We sum up the inequalities for all $(u, v) \in \delta(S)$ - \item This gives us - \begin{align} - \sum_i \lambda_i \sum_{\structure{(u, v) \in \delta(S)}} \sum_{\substack{e_T \in T_i:\\\structure{(u,v)} \in P_i(e_T)}} C_i(e_T) \leq \Oh(\log n)c(\delta(S)) - \end{align} - \item We are done with the observation that - \begin{align} - c_{T_i}(\delta(S)) = \sum_{\substack{e_T \in E_{T_i}:\\e_T \in \delta(S)}} C_i(e_T) \leq \sum_{\structure{(u, v) \in \delta(S)}} \sum_{\substack{e_T \in T_i:\\\structure{(u,v)} \in P_i(e_T)}} C_i(e_T) - \end{align} - } - \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{Approximation Algorithm} - - \begin{block}{Minimum Bisection Approximation} - Given graph $G = (V, E)$ and cost function $c : E \to \R^+$. - \begin{enumerate} - \item Interpret costs $c(e)$ as \structure{capacities} - \item Solve oblivious routing on $G$, obtaining \structure{trees $T_i$} - \item Find minimum \structure{tree bisections $X_i$} for all trees $T_i$ - \item Choose the $X_i$ with \structure{lowest $c(\delta(X_i))$} - \end{enumerate} - \end{block} - - \vfill - - \begin{itemize} - \item Let now $X^*, X_i$ be the optimal solutions on $G$ and the $T_i$. Then - \begin{align} - \sum_i \lambda_i c(\delta(X_i)) &\leq \sum_i \lambda_i c_{T_i}(\delta(X_i)) \\ - &\leq \sum_i \lambda_i c_{T_i}(\delta(X^*)) \\ - &\leq \Oh(\log n) c(\delta(X^*)) - \end{align} - \item This also holds for the \structure{best $X_i$}, giving an \alert{$\Oh(\log n)$-approximation} - \item How to find the $X_i$? - \end{itemize} -\end{frame} - -\end{document}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/minimum_bisection/presentation/beamerthemeLEA2.sty Sat Jul 05 17:27:53 2014 +0200 @@ -0,0 +1,61 @@ +\ProvidesPackage{beamerthemeLEA2} + +\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} + +%% shadow, font, color, outer, inner +%% normal text, alerted text, example text, structure + +\useoutertheme{split} + +\setbeamercolor{normal text}{fg=black,bg=white} +\setbeamercolor{alerted text}{fg=tumred,bg=white} +\setbeamercolor{example text}{fg=tumgreen,bg=white} +\setbeamercolor{structure}{fg=tumblue,bg=white} +\setbeamercolor{titlelike}{fg=tumblue} +\setbeamercolor{subtitle}{fg=black} +\setbeamerfont{title}{series=\bfseries} + +\setbeamertemplate{sections/subsections in toc}[square] +\setbeamertemplate{items}[square] +\setbeamertemplate{navigation symbols}[only frame symbol] + +\setbeamertemplate{blocks}[default] + +\setbeamercolor{block title} {use=normal text, fg=black,bg=tumlightblue} +\setbeamercolor{block title alerted}{use=alerted text,fg=white,bg=alerted text.fg} +\setbeamercolor{block title example}{use=example text,fg=white,bg=example text.fg} + +\setbeamercolor{block body} {parent=normal text,use=block title, bg=block title.bg!25!bg} +\setbeamercolor{block body alerted}{parent=normal text,use=block title alerted,bg=block title.bg!25!bg} +\setbeamercolor{block body example}{parent=normal text,use=block title example,bg=block title example.bg!15!bg} + +%\pgfdeclareimage[height=5mm]{uni}{TU_Muenchen_Logo_Breit} +\pgfdeclareimage[height=5mm]{uni}{tum} +\logo{\pgfuseimage{uni}} + +\defbeamertemplate*{footline}{infolines theme}{% + \hspace*{2ex}\raisebox{1.5ex}[-1.5ex]{% + \tiny\insertframenumber{}/\inserttotalframenumber \hspace{5mm} \insertnavigation{0.8\paperwidth}}% +} + +\setbeamertemplate{frametitle}{ + \begin{beamercolorbox}[wd=\textwidth,leftskip=0mm]{frametitle} + \usebeamerfont*{frametitle} + \insertframetitle\hfill\parbox{10mm}{\vspace{-1.5mm}\insertlogo} + \end{beamercolorbox} + \vspace{-2.5mm}\textcolor{tumblue}{\noindent\rule{\textwidth}{0.4px}} +} +% hier kein Logo +\setbeamertemplate{sidebar right}{}%{\vfill\vskip2pt\llap{\usebeamertemplate***{navigation symbols}\hskip1mm}\vskip2pt} + +\setbeamertemplate{headline}{} + +\setbeamercovered{transparent} + +% escapeinside= removed for utf8 compatibility +\lstset{numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\small, backgroundcolor=\color{tumlightblue}}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/minimum_bisection/presentation/preamble.tex Sat Jul 05 17:27:53 2014 +0200 @@ -0,0 +1,54 @@ +\documentclass[compress, 9pt, german, t]{beamer} +\usepackage{etex} + +\usepackage[english]{babel} +\uselanguage{English} +\languagepath{English} + +\usepackage[T1]{fontenc} +\usepackage[utf8]{inputenc} + +\usepackage{arev} +\usepackage{mathpazo} +\usepackage{microtype} + +\usepackage{url} +\usepackage{listings} +\usepackage{xcolor} +\usepackage{tabu} +\usepackage{tikz} +\usepackage{pgfplots} +\pgfplotsset{compat=1.9} +\usetikzlibrary{shapes} +\usetikzlibrary{fit} + +\usepackage{amsmath} +\usepackage{mathdots} +\usepackage{mathtools} +\mathtoolsset{showonlyrefs,showmanualtags} +\usepackage{mathrsfs} +\usepackage{csquotes} + +\usepackage{todonotes} + +\usepackage{beamerthemeLEA2} +\setbeamercovered{transparent} + +\newcommand{\N}{\mathbb{N}} +\newcommand{\Z}{\mathbb{Z}} +\newcommand{\Q}{\mathbb{Q}} +\newcommand{\R}{\mathbb{R}} +\newcommand{\C}{\mathbb{C}} +\newcommand{\Prob}{\mathrm{P}} +\newcommand{\Oh}{\mathcal{O}} +\newcommand{\Ih}{\mathcal{I}} +\newcommand{\Ell}{\mathcal{L}} + +\newcommand{\abs}[1]{\left\vert #1 \right\vert} +\newcommand{\powerset}[1]{\mathcal{P}\left( #1 \right)} +\newcommand{\setnot}[1]{\overline{#1}} +\newcommand{\setsymdiff}{\,\triangle\,} + +\newcommand{\defeq}{\coloneqq} %Mathtools already defines this + +\DeclareMathOperator{\st}{s.t.}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/minimum_bisection/presentation/presentation.tex Sat Jul 05 17:27:53 2014 +0200 @@ -0,0 +1,1014 @@ +\input{preamble.tex} +\input{tikzpictures.tex} + +\title{Oblivious Routing and Minimum Bisection} +\subtitle{Seminar: Approximation Algorithms} +\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} +\date{June 3, 2014} + +\begin{document} +\begin{frame} + \titlepage +\end{frame} + +\begin{frame} + \frametitle{Flow Problems} + \begin{problem}[Single Commodity Flow] + Given + \begin{itemize}[<+->] + \item An (un)directed Graph $G = (V, E)$ + \item A \structure{capacity function} $c : E \to \R^+$ + \item A source $s$ and a target $t$ + \end{itemize} + \uncover<4->{Calculate a maximum possible \structure{flow} $f : E \to \R^+$ through $G$.} + \end{problem} + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges[directed] + \only<2->{\flowcapacities} + + \draw<3-> + (n.south) node[below] {\structure{s}} + (j.south) node[below] {\structure{t}}; + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Flow Problems} + + \begin{problem}[Multi Commodity Flow] + Given + \begin{itemize} + \item An undirected Graph $G = (V, E)$ + \item A capacity function $c : E \to \R^+$ + \item<2-> A \structure{demand function} $d : V^2 \to \R^+$ + \end{itemize} + \uncover<3->{Calculate a flow $f$ with least \structure{congestion $\rho = \max_{e \in E}\frac{f_e}{c_e}$}.} + \end{problem} + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowcapacities + \only<2->{\flowdemands} + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Oblivious Routing} + + \begin{problem}[Oblivious Routing] + Given + \begin{itemize} + \item An undirected Graph $G = (V, E)$ + \item A capacity function $c : E \to \R^+$ + \end{itemize} + Calculate a combination of paths for each $(u, v) \in V^2$ such that for \alert{any} demand function the \structure{congestion} will be as small as possible. + \end{problem} + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowcapacities + + \draw<2-> + (n.south) node[below] {\structure{u}} + (j.south) node[below] {\structure{v}}; + + \only<3-> { + \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} + + \path[font=\Large] + (n) + +(-0.5, 0.5) node[tumgreen] {$\frac{1}{4}$} + +(-0.5, 0) node[tumblue] {$\frac{1}{2}$} + +(-0.5, -0.5) node[tumred] {$\frac{1}{4}$}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Routing with a Spanning Tree} + + \begin{itemize} + \item Choose any \structure{spanning tree $T$} of $G$ + \item Routing along its unique paths is a feasible solution + \end{itemize} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges + + \only<2-> { + \draw + (l) node[above right] {\structure{u}} + (i) node[above right] {\structure{v}}; + \begin{pgfonlayer}{demand} + \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i); + \end{pgfonlayer} + } + + \only<3-> { + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in {l/m,m/e,e/d,d/k,k/j,j/i} + \draw[tree edge, tumred] (\source.center) edge (\dest.center); + \end{pgfonlayer} + } + + \only<4-> { + \flowcapacities + \node[below=0 of b] {\structure{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{10}{2} = 5$}}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Tree Splits} + + \begin{itemize} + \item Removing one edge $e_T$ from a ST creates a \structure{node partition $S(e_T)$} + \item Every such partition has a \structure{capacity $C(e_T)$} + \item And a \structure{demand $D(e_T)$} + \end{itemize} + \begin{align} + C(e_T) &= \sum_{\substack{u \in S(e_T), \\ v \not\in S(e_T)}} c_{uv} & + D(e_T) &= \sum_{\substack{u \in S(e_T), \\ v \not\in S(e_T)}} c_{uv} + \end{align} + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges + + \only<2-> { + \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=3pt] (el) {}; + \end{pgfonlayer} + + \path (el) + ++ (200:1.5) + ++ (0, -0.5) coordinate (label); + \node[below=0 of label] {\structure{$S(\alert{e_T})$}}; + } + + \only<3> { + \flowcapacities + + \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} + } + + \only<3-> { + \node[below=0.5 of label] {$C(e_T) = 10$}; + } + + \only<4-> { + \flowdemands + + \begin{pgfonlayer}{demand} + \foreach \source/\dest/\demand/\pos/\bendage in { + {n/j/10/0.2/right}, + {n/h/12/0.7/left}, + {k/m/5/0.8/right}} + \draw[demand edge, bend \bendage=15, tumorange] (\source) edge node[flow demand, text=tumorange, pos=\pos]{\demand} (\dest); + \end{pgfonlayer} + + \node[below=1 of label] {$D(e_T) = 27$}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Optimal Solution} + + \begin{lemma} + For any tree $T$ and any tree edge $e_T$, we know that for \alert{any routing} in $G$ there must be an edge with \structure{congestion} + \begin{align} + \rho_e \geq \frac{D(e_T)}{C(e_T)} + \end{align} + And therefore the \structure{optimal solution $\rho^\ast$} can be no better. + \end{lemma} + + \vfill + \pause + + \begin{itemize} + \item Suppose we find a tree such that for some $\alpha$ + \begin{align} + \forall e_T \in E_T.\quad c_{e_T} \geq \frac{1}{\alpha} C(e_T) + \end{align} + \item Then we have + \begin{align} + \structure{\rho_T} = \max_{e_T} \frac{D(e_T)}{c_{e_T}} \structure{\leq} \alpha \max_{e_T} \frac{D(e_T)}{C(e_T)} \leq \structure{\alpha \rho^\ast} + \end{align} + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Routing with multiple Spanning Trees} + + \begin{itemize} + \item Choose a \structure{set of spanning trees $\left\{ T_i \right\}$} of $G$ + \item And a \structure{convex combination $\lambda$} with $\sum_i \lambda_i = 1$, $\lambda \geq 0$ + \item Routing is now split according to this combination. For $e \in E$ + \begin{align} + f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e) + \end{align} + \end{itemize} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + + \draw + (l) node[above right] {\structure{u}} + (i) node[above right] {\structure{v}}; + + \path + (n) + ++ (-1, -0.5) coordinate (label); + + \only<2> { + \flowtreeedges + } + + \only<2-> { + \node[tumgreen, below=0 of label, anchor=west] {$\displaystyle\lambda_1 = \frac{1}{2}$}; + } + + \only<3> { + \flowtreeedgestwo[tumorange] + } + + \only<3-> { + \node[tumorange, below=0.5 of label, anchor=west] {$\displaystyle\lambda_2 = \frac{1}{2}$}; + } + + \only<4-> { + \begin{pgfonlayer}{demand} + \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i); + \end{pgfonlayer} + + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in {l/m,m/e,e/d,d/k,k/j,j/i} + \draw[tree edge, tumgreen] (\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} + } + + \only<5-> { + \flowcapacities + \node[below=1 of label, anchor=west] {\structure{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{5}{2} = 2.5$}}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Routing with multiple Spanning Trees} + + \begin{itemize} + % \item Remember that the total flow on edge $e \in E$ is + % \begin{align} + % f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e) + % \end{align} + \item Suppose we now find a \structure{set of trees} such that for some $\alpha$ + \begin{align} + \forall e \in E.\quad c_{e} \geq \frac{1}{\alpha} \sum_{\substack{i:\\e \in T_i}} \lambda_i C_i(e) + \end{align} + \vfill + \item Then we have + \begingroup + \addtolength{\jot}{.5em} + \begin{align} + \structure{\rho} &= \hphantom{\alpha}\max_{e} \frac{f(e)}{c_{e}} \\ + &= \hphantom{\alpha}\max_{e} \frac{\sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)}{c_e} \\ + &\structure{\leq} \alpha \max_{e} \frac{\sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)}{\sum_{\substack{i:\\e \in T_i}} \lambda_i C_i(e)} \\ + &\leq \alpha \max_{e} \max_{i} \frac{D_i(e)}{C_i(e)} \leq \structure{\alpha \rho^\ast} + \end{align} + \endgroup + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Pathtrees} + + \begin{itemize} + \item Identify every edge in a tree with a \structure{path} in $G$ + \item These paths can \structure{overlap} + \item For tree $T$ we get a mapping $P_T : E_T \to E^+$ + \end{itemize} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges + \flowcapacities + + \draw + (e) node[above right] {\structure{a}} + (d) node[above=0.1] {\structure{b}}; + + \only<2-> { + \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} + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Routing with multiple Pathtrees} + + \begin{itemize} + \item Choose a \structure{set of pathtrees $\left\{ T_i \right\}$} of $G$ with \structure{combination $\lambda$} + \item Now route along the paths identified with edges. For $e \in E$ + \begin{align} + f(\structure{e}) &= \sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(\alert{e_T})}} D_i(\alert{e_T}) + \end{align} + \end{itemize} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + + \draw + (l) node[above right] {\structure{u}} + (i) node[above right] {\structure{v}}; + + \path + (n) + ++ (-1, -0.5) coordinate (label); + + \only<2> { + \flowtreeedges + } + + \only<2-> { + \node[tumgreen, below=0 of label, anchor=west] {$\displaystyle\lambda_1 = \frac{2}{3}$}; + } + + \only<3> { + \flowtreeedgestwo[tumorange] + } + + \only<3-> { + \node[tumorange, below=0.5 of label, anchor=west] {$\displaystyle\lambda_2 = \frac{1}{3}$}; + } + + \only<4-> { + \begin{pgfonlayer}{demand} + \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{9} (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} + } + + \only<5-> { + \flowcapacities + \node[below=1 of label, anchor=west] {\structure{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{6}{4} = 2$}}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Routing with multiple pathtrees} + + \begin{itemize} + \item Again suppose we now find a \structure{set of trees} such that for some $\alpha$ + \begin{align} + \forall \structure{e} \in E.\quad c_{e} \geq \frac{1}{\alpha} \sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(\alert{e_T})}} C_i(\alert{e_T}) + \end{align} + \item Then we have + \begingroup + \addtolength{\jot}{.5em} + \begin{align} + \rho &= \hphantom{\alpha}\max_{\structure{e}} \frac{f(\structure{e})}{c_{\structure{e}}} \\ + &\leq \alpha \max_{\structure{e}} \frac{\sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(e_T)}} D_i(\alert{e_T})}{\sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(e_T)}} C_i(\alert{e_T})} \\ + &\leq \alpha \max_{\structure{e}} \max_{i} \frac{D_i(\structure{e})}{C_i(\structure{e})} \leq \alpha \rho^\ast + \end{align} + \endgroup + \end{itemize} + + \vfill + + \only<2> { + \begin{center} + How do we find such a set of trees? How large is $\alpha$? + \end{center} + } +\end{frame} + +\begin{frame} + \frametitle{Primal program} + + \begin{block}{Primal Program} + Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.\\ + We want to find the best trees with smallest $\alpha$. + \begin{alignat}{3} + \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\ + \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} + \end{block} + + \vfill + + \begin{center} + We want to show that $\alpha \in \Oh(\log n)$ + \end{center} +\end{frame} + +\begin{frame} + \frametitle{Dual Program} + + \begin{block}{Dual Program} + Let $\Ih$ be the exponentially large set of \structure{all pathtrees}. + \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} + \end{block} + + \vfill + + \begin{center} + If $z \in \Oh(\log n)$ then $\alpha \in \Oh(\log n)$ by strong duality + \end{center} +\end{frame} + +\begin{frame} + \frametitle{Solution of the Dual Program} + + \begin{block}{Dual Program} + Let $\Ih$ be the exponentially large set of \structure{all pathtrees}. + \begin{alignat}{3} + \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ % + \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\ + \only<-2>{ + && \structure{z} & \leq \sum_{e_T \in T_i} C_i(e_T) \tikzmark{a}\sum_{(u,v) \in P_i(e_T)} \structure{\ell_{uv}} \tikzmark{b} & \qquad \forall i \in \Ih \\ + } + \only<3-4>{ + && \structure{z} & \leq \tikzmark{c}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)\tikzmark{d} & \qquad \forall i \in \Ih \\ + } + \only<5->{ + && \structure{z} & \leq \min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)\\ + } + && \structure{\Ell} &\geq 0 + \end{alignat} + \end{block} + + \vfill + + \begin{itemize} + \item We interpret the $\structure{\ell_{uv}}$ as edge lengths in $G$ + \item They define a \structure{shortest path metric $d_{\structure{\ell}}(u, v)$} + \item For an edge $e = (x, y)$ we write $d_{\structure{\ell}}(e) \defeq d_{\structure{\ell}}(x, y)$ + \end{itemize} + \begin{tikzpicture}[remember picture, overlay] + \only<2> {% + \node[fit=(a)(b), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below:{$\geq d_{\structure{\ell}}(e_T)$}}] {}; + } + \only<4> {% + \node[fit=(c)(d), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below right:{$\geq \min_{i \in \Ih} \cdots$}}] {}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Solution of the Dual Program} + + \begin{block}{Dual Program} + Let $\Ih$ be the exponentially large set of \structure{all pathtrees}. + \only<1-2>{% + \begin{alignat}{3} + \max_{\structure{\Ell}} \quad & \mathrlap{\min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)}\\ + \st \quad && \tikzmark{a}\sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1\tikzmark{b} \\ + && \structure{\Ell} &\geq 0 + \end{alignat} + \vspace{-1em} + } + \only<3>{% + \begin{alignat}{3} + \max_{\structure{\Ell}} \quad & \min_{i \in \Ih}\frac{\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)}{\sum_{u, v \in V} c_{uv} \structure{\ell_{uv}}}\\ + \st \quad & \structure{\Ell} \geq 0 + \end{alignat} + } + \end{block} + + \vfill + + \uncover<2-3>{ + \begin{itemize} + \item Now suppose + \begin{align} + \sum_{u, v \in V} c_{uv} \ell_{uv} = \beta > 0 + \end{align} + \item If we scale every length by $\frac{1}{\beta}$ our solution will change by $\frac{1}{\beta}$ + \end{itemize} + } + \begin{tikzpicture}[remember picture, overlay] + \only<2>{ + \node[fit=(a)(b), highlight, minimum height=2.5em, inner sep=-3pt] {}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Tree Metric} + + \begin{theorem}[Tree Metric] + For our metric $d_\ell$ there exists a \structure{tree metric $(V, M)$} with + \begingroup + \addtolength{\jot}{.5em} + \begin{alignat}{2} + d_\ell(u, v) &\leq M_{uv} & \forall u, v \in V\\ + \sum_{u, v \in V} c_{uv} M_{uv} &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v) + \end{alignat} + \endgroup + \end{theorem} + + \vfill + + \centering + \begin{tikzpicture}[grow=down, level distance = 25] + \begin{scope} + \tikzstyle{every node} = [draw, flow node] + \tikzstyle{edge from parent} = [draw, edge] + + \tikzstyle{level 1} = [sibling distance = 100] + \tikzstyle{level 2} = [sibling distance = 50] + \tikzstyle{level 3} = [sibling distance = 30] + \node[label=above:$z$] (z) {} + child { + node[label=above left:$y$] (y) {} + edge from parent + child { + node[label=above left:$x$] (x) {} + edge from parent + child { + node[label=below left:$\structure{u}$] (u) {} + edge from parent + } + child { + node {} + edge from parent + } + } + child { + node {} + edge from parent + child { + node {} + edge from parent + } + child { + node {} + edge from parent + } + } + } + child { + node[label=above right:$\structure{v}$] (v) {} + edge from parent + child { + node {} + edge from parent + child { + node {} + edge from parent + } + child { + node {} + edge from parent + } + } + child { + node {} + edge from parent + child { + node {} + edge from parent + } + child { + node {} + edge from parent + } + } + }; + \end{scope} + + \begin{pgfonlayer}{marked} + \foreach \source/\dest in {u/x,x/y,y/z,z/v} + \draw [tree edge, tumred] (\source.center) -- (\dest.center); + \end{pgfonlayer} + + \node at (0, -3.5) {$M_{uv} = M_{ux} + M_{xy} + M_{yz} + M_{zv}$}; + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Sum over all capacities} + + \begin{lemma}[] + Let $T$ be a spanning tree and $(V, M)$ a tree metric of $G = (V, E)$. Then + \begin{align} + \sum_{(x, y) \in E_T} C(x, y) M_{xy} = \sum_{(u, v) \in E} c_{uv} M_{uv} + \end{align} + \end{lemma} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges + + \draw + (n) node[above=0.1] {\structure{u}} + (m) node[below=0.05] {a} + (e) node[below=0.05] {b} + (d) node[above=0.1] {c} + (c) node[below=0.05] {d} + (b) node[above=0.1] {\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} + + \only<2> { + \begin{pgfonlayer}{marked} + \draw[tree edge, tumred] (n.center) edge (m.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(n), inner sep=15pt] (el) {}; + \end{pgfonlayer} + } + \only<3> { + \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=3pt] (el) {}; + \end{pgfonlayer} + } + \only<4> { + \begin{pgfonlayer}{marked} + \draw[tree edge, tumred] (e.center) edge (d.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m)(e)(f), inner sep=3pt] (el) {}; + \end{pgfonlayer} + } + \only<5> { + \begin{pgfonlayer}{marked} + \draw[tree edge, tumred] (d.center) edge (c.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=-10, fit=(c)(b), inner sep=3pt] (el) {}; + \end{pgfonlayer} + } + \only<6> { + \begin{pgfonlayer}{marked} + \draw[tree edge, tumred] (c.center) edge (b.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(b), inner sep=15pt] (el) {}; + \end{pgfonlayer} + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Value of the Dual Problem} + + \begin{block}{Dual Program} + Let $\Ih$ be the exponentially large set of \structure{all pathtrees}. + \begin{alignat}{3} + \max_{\structure{\Ell}} \quad & \min_{i \in \Ih}\frac{\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)}{\sum_{u, v \in V} c_{uv} \structure{\ell_{uv}}}\\ + \st \quad & \structure{\Ell} \geq 0 + \end{alignat} + \end{block} + + For any $\Ell$ we know that for the \structure{minimizing tree $T_i$} holds + \begin{align} + \sum_{e_T \in T_i} C_i(e_T) d_\ell(e_T) &\leq \sum_{e_T \in T_i} C_i(e_T) M_{e_T} \\ + &= \sum_{u, v \in V} c_{uv} M_{uv} \\ + &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v) \\ + &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} \ell_{uv} \\ + \frac{\sum_{e_T \in T_i} C_i(e_T) d_\ell(e_T)}{\sum_{u, v \in V} c_{uv} \ell_{uv}} &\leq \Oh(\log n) + \end{align} +\end{frame} + +\begin{frame} + \frametitle{Value of the Primal Program} + + \begin{block}{Primal Program} + Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.\\ + We want to find the best trees with smallest $\alpha$. + \begin{alignat}{3} + \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\ + \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} + \end{block} + + \vfill + + \begin{itemize} + \item There is a $\structure{\lambda}$ such that $\structure{\alpha \in \Oh(\log n)}$ + \item But why are polynomially many trees enough? + \item This gives an \alert{$\Oh(\log n)$-approximation} + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Minimum Bisection} + + \begin{problem}[Minimum Bisection] + Given + \begin{itemize} + \item An undirected Graph $G = (V, E)$ + \item A cost function $c : E \to \R^+$ + \end{itemize} + Find a set $S \subset V$ containing half the vertices with \structure{minimal split cost}. + \end{problem} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowcapacities + + \only<2-> { + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {}; + \end{pgfonlayer} + + \path (el) + ++ (-30:2.3) node {\structure{$S$}}; + } + + \only<3-4> { + \begin{pgfonlayer}{marked} + \foreach \source/\dest in {b/j,b/c,c/f,e/c,e/d,e/g,h/i} + \draw [tree edge, tumorange] (\source.center) -- (\dest.center); + \end{pgfonlayer} + + \path (n) + ++ (-0.5, -1.5) node[tumorange, anchor=west] {\alt<3>{$\hphantom{c(}\delta(S)$}{$c(\delta(S)) = 25$}}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Approximation Algorithm} + + \begin{block}{Minimum Bisection Approximation} + Given graph $G = (V, E)$ and cost function $c : E \to \R^+$. + \begin{enumerate} + \item Interpret costs $c(e)$ as \structure{capacities} + \item Solve oblivious routing on $G$, obtaining \structure{trees $T_i$} + \item Find minimum \structure{tree bisections $X_i$} for all trees $T_i$ + \item Choose the $X_i$ with \structure{lowest $c(\delta(X_i))$} + \end{enumerate} + \end{block} + + \vfill + \pause + + We have to show + \begin{itemize} + \item What the $X_i$ actually are + \item An \alert{$\Oh(\log n)$-approximation} guarantee + \item That we can find the $X_i$ in polynomial time + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Tree Bisections} + + \begin{itemize} + \item Given a spanning tree $T$ of $G$ with an edge $e_T \in E_T$ + \item Define a new \structure{cost function $c_T$} using tree splits + \end{itemize} + \begin{align} + c_T(e_T) &= C(e_T) & c_T(\delta(S)) = \sum_{\substack{e_T \in E_T:\\e_T \in \delta(S)}} C(e_T) + \end{align} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges + + \only<2-> { + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {}; + \end{pgfonlayer} + + \path (el) + ++ (-30:2.3) node {\structure{$S$}}; + } + + \only<3> { + \begin{pgfonlayer}{marked} + \foreach \source/\dest in {b/c,e/d,h/i} + \draw [tree edge, tumred] (\source.center) -- (\dest.center); + \end{pgfonlayer} + + \foreach \source/\dest/\name in {b/c/$e_3$,e/d/$e_2$,h/i/$e_1$} + \path (\source) -- node[node on edge] {\name} (\dest); + + \path (n) + ++ (-1, -1.5) node[tumred, anchor=west] {$\displaystyle c_T(\delta(S)) = \sum_{k=1}^3 C(e_k)$}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Tree Bisections} + + \begin{lemma}[] + For any spanning tree $T$ and any $S \subseteq V$ we have + \begin{align} + c(\delta(S)) \leq c_T(\delta(S)) + \end{align} + \end{lemma} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges + + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {}; + \end{pgfonlayer} + + \path (el) + ++ (-30:2.3) node {\structure{$S$}}; + + \draw + (b) node[below=0.05] {\structure{u}} + (j) node[below=0.05] {\structure{v}}; + + \begin{pgfonlayer}{marked} + \foreach \source/\dest in {b/j,f/c,e/c,e/g} + \draw [tree edge, tumblue, dash pattern=on 7pt off 7pt] (\source.center) -- (\dest.center); + + \foreach \source/\dest in {b/c,e/d,h/i} + \draw [tree edge, tumred] (\source.center) -- (\dest.center); + \end{pgfonlayer} + + \foreach \source/\dest/\name in {b/c/$e_3$,e/d/$e_2$,h/i/$e_1$} + \path (\source) -- node[node on edge] {\name} (\dest); + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Tree Bisections} + + \begin{lemma}[] + Let $\left\{ T_i \right\}$ be a solution to the \structure{oblivious flow} problem on $G$.\\ + Then for any $S \subseteq V$ we have + \begin{align} + \sum_i \lambda_i c_{T_i}(\delta(S)) \leq \Oh(\log n) c(\delta(S)) + \end{align} + \end{lemma} + + \vfill + + \begin{itemize} + \only<1> { + \item Remember from the primal program that \structure{for all $u, v \in V$} + \begin{align} + \sum_i \lambda_i \sum_{\substack{e_T \in T_i:\\\structure{(u,v)} \in P_i(e_T)}} C_i(e_T) \leq \Oh(\log n) \structure{c_{uv}} + \end{align} + \item We sum up the inequalities for all $(u, v) \in \delta(S)$ + } + \only<2> { + \item We sum up the inequalities for all $(u, v) \in \delta(S)$ + \item This gives us + \begin{align} + \sum_i \lambda_i \sum_{\structure{(u, v) \in \delta(S)}} \sum_{\substack{e_T \in T_i:\\\structure{(u,v)} \in P_i(e_T)}} C_i(e_T) \leq \Oh(\log n)c(\delta(S)) + \end{align} + \item We are done with the observation that + \begin{align} + c_{T_i}(\delta(S)) = \sum_{\substack{e_T \in E_{T_i}:\\e_T \in \delta(S)}} C_i(e_T) \leq \sum_{\structure{(u, v) \in \delta(S)}} \sum_{\substack{e_T \in T_i:\\\structure{(u,v)} \in P_i(e_T)}} C_i(e_T) + \end{align} + } + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Approximation Algorithm} + + \begin{block}{Minimum Bisection Approximation} + Given graph $G = (V, E)$ and cost function $c : E \to \R^+$. + \begin{enumerate} + \item Interpret costs $c(e)$ as \structure{capacities} + \item Solve oblivious routing on $G$, obtaining \structure{trees $T_i$} + \item Find minimum \structure{tree bisections $X_i$} for all trees $T_i$ + \item Choose the $X_i$ with \structure{lowest $c(\delta(X_i))$} + \end{enumerate} + \end{block} + + \vfill + + \begin{itemize} + \item Let now $X^*, X_i$ be the optimal solutions on $G$ and the $T_i$. Then + \begin{align} + \sum_i \lambda_i c(\delta(X_i)) &\leq \sum_i \lambda_i c_{T_i}(\delta(X_i)) \\ + &\leq \sum_i \lambda_i c_{T_i}(\delta(X^*)) \\ + &\leq \Oh(\log n) c(\delta(X^*)) + \end{align} + \item This also holds for the \structure{best $X_i$}, giving an \alert{$\Oh(\log n)$-approximation} + \item How to find the $X_i$? + \end{itemize} +\end{frame} + +\end{document}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/minimum_bisection/presentation/tikzpictures.tex Sat Jul 05 17:27:53 2014 +0200 @@ -0,0 +1,101 @@ +\pgfdeclarelayer{background} +\pgfdeclarelayer{demand} +\pgfdeclarelayer{marked} +\pgfdeclarelayer{foreground} +\pgfsetlayers{background,demand,marked,main,foreground} + +\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 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{tree edge} = [marked edge, tumgreen] +\tikzstyle{flow capacity} = [node on edge] +\tikzstyle{flow demand} = [node on edge, text=tumred] + +\tikzstyle{highlight} = [draw=tumorange, very thick, rounded corners] + +\newcommand{\tikzmark}[1]{\tikz[overlay,remember picture,baseline] \node [anchor=base] (#1) {};} + +\newcommand{\flownodes}{% + \pgfmathsetseed{42} + \def\jiggliness{0.2} + \def\jiggle{++ (rand * \jiggliness, rand * \jiggliness)} + + \path[use as bounding box] (-4, 2.7) rectangle (3.5,6.15); + + \foreach \pos/\name in { + % {(0,1)/a}, + {(-0.5,2.75)/b}, + {(0.5,3.25)/c}, + {(0.75,4)/d}, + {(-0.5,4.5)/e}, + {(-1.25,3.75)/f}, + {(1.5,4.75)/g}, + {(0,5.5)/h}, + {(2.5,5.5)/i}, + {(3.5,3.5)/j}, + {(2.25,4)/k}, + {(-2,6)/l}, + {(-2.5,5)/m}, + {(-4,5)/n}} + \draw \pos\jiggle node[flow node] (\name) {}; + % \draw \pos\jiggle node[flow node, label={\name}, font=\footnotesize] (\name) {}; +} +\newcommand{\flowedges}[1][]{% + \foreach \source/\dest in { + % {a/b}, {a/n}, {a/j}, + {n/b}, {b/j}, {f/b}, {c/b}, + {c/d}, {e/d}, {e/f}, {g/i}, + {h/e}, {h/i}, {i/j}, {k/j}, + {l/h}, {l/m}, {n/m}, + {c/k}, {k/i}, {g/d}, {m/e}, {n/l}, + {m/f}, {f/c}, {d/k}, {e/g}, {c/e}} + \draw[flow edge, #1] (\source) -- (\dest); +} +\newcommand{\flowcapacities}[1][]{% + \foreach \source/\dest/\capacity in { + % {a/b}, {a/n}, {a/j}, + {n/b/2}, {b/j/10}, {c/b/3}, {f/b/4}, + {c/d/4}, {e/d/2}, {e/f/4}, {g/i/2}, + {h/e/1}, {h/i/2}, {i/j/6}, {k/j/4}, + {l/h/3}, {l/m/4}, {n/m/5}, + {c/k/4}, {k/i/3}, {g/d/1}, {m/e/4}, {n/l/6}, + {m/f/1}, {f/c/2}, {d/k/4}, {e/g/1}, {c/e/5}} + \path (\source) -- node[flow capacity, #1]{\capacity} (\dest); +} +\newcommand{\flowdemands}{% + \begin{pgfonlayer}{demand} + \foreach \source/\dest/\demand/\pos/\bendage in { + {n/j/10/0.2/right}, + {h/j/8/0.2/left}, + {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); + \end{pgfonlayer} +} +\newcommand{\flowtreeedges}[1][]{% + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in { + % {a/b}, + {c/b}, + {c/d}, {e/d}, {e/f}, {g/i}, + {m/e}, {d/k}, {i/j}, {k/j}, + {h/i}, {l/m}, {n/m}} + \draw [tree edge, #1] (\source.center) -- (\dest.center); + \end{pgfonlayer} +} +\newcommand{\flowtreeedgestwo}[1][]{% + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in { + {n/l}, {l/h}, {h/i}, {i/g}, {i/j}, + {j/k}, {g/d}, {d/c}, {g/e}, {c/f}, + {f/m}, {f/b}} + \draw[tree edge, #1] (\source.center) -- (\dest.center); + \end{pgfonlayer} +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/minimum_bisection/presentation/tum.pdf Sat Jul 05 17:27:53 2014 +0200 @@ -0,0 +1,84 @@ +%PDF-1.4 +%쏢 +5 0 obj +<</Length 6 0 R/Filter /FlateDecode>> +stream +xmMj!ཧ/ֿu"=Cthz S(Wc~{߶P~ |7,u(Mh DF%+E[̑T +XJ[B&Ri%WJ%*R&NRͩK Q)Fƾ& M.d\i s?9_x}[Yendstream +endobj +6 0 obj +172 +endobj +4 0 obj +<</Type/Page/MediaBox [0 0 54 29] +/Parent 3 0 R +/Resources<</ProcSet[/PDF] +/ExtGState 8 0 R +>> +/Contents 5 0 R +>> +endobj +3 0 obj +<< /Type /Pages /Kids [ +4 0 R +] /Count 1 +>> +endobj +1 0 obj +<</Type /Catalog /Pages 3 0 R +/Metadata 9 0 R +>> +endobj +7 0 obj +<</Type/ExtGState +/OPM 1>>endobj +8 0 obj +<</R7 +7 0 R>> +endobj +9 0 obj +<</Type/Metadata +/Subtype/XML/Length 1448>>stream +<?xpacket begin='' id='W5M0MpCehiHzreSzNTczkc9d'?> +<?adobe-xap-filters esc="CRLF"?> +<x:xmpmeta xmlns:x='adobe:ns:meta/' x:xmptk='XMP toolkit 2.9.1-13, framework 1.6'> +<rdf:RDF xmlns:rdf='http://www.w3.org/1999/02/22-rdf-syntax-ns#' xmlns:iX='http://ns.adobe.com/iX/1.0/'> +<rdf:Description rdf:about='uuid:c9ca2823-6786-11ee-0000-81ba9e8eeeec' xmlns:pdf='http://ns.adobe.com/pdf/1.3/' pdf:Producer='GPL Ghostscript 9.10'/> +<rdf:Description rdf:about='uuid:c9ca2823-6786-11ee-0000-81ba9e8eeeec' xmlns:xmp='http://ns.adobe.com/xap/1.0/'><xmp:ModifyDate>2013-10-07T18:05:09+02:00</xmp:ModifyDate> +<xmp:CreateDate>2013-10-07T18:05:09+02:00</xmp:CreateDate> +<xmp:CreatorTool>Adobe Illustrator(R) 8.0</xmp:CreatorTool></rdf:Description> +<rdf:Description rdf:about='uuid:c9ca2823-6786-11ee-0000-81ba9e8eeeec' xmlns:xapMM='http://ns.adobe.com/xap/1.0/mm/' xapMM:DocumentID='uuid:c9ca2823-6786-11ee-0000-81ba9e8eeeec'/> +<rdf:Description rdf:about='uuid:c9ca2823-6786-11ee-0000-81ba9e8eeeec' xmlns:dc='http://purl.org/dc/elements/1.1/' dc:format='application/pdf'><dc:title><rdf:Alt><rdf:li xml:lang='x-default'>(TUMLogo_oZ_Vollfl_blau_CMYK.eps)</rdf:li></rdf:Alt></dc:title><dc:creator><rdf:Seq><rdf:li>(Florian) ()</rdf:li></rdf:Seq></dc:creator></rdf:Description> +</rdf:RDF> +</x:xmpmeta> + + +<?xpacket end='w'?> +endstream +endobj +2 0 obj +<</Producer(GPL Ghostscript 9.10) +/CreationDate(D:20131007180509+02'00') +/ModDate(D:20131007180509+02'00') +/Creator(Adobe Illustrator\(R\) 8.0) +/Author(\(Florian\) \(\)) +/Title(\(TUMLogo_oZ_Vollfl_blau_CMYK.eps\))>>endobj +xref +0 10 +0000000000 65535 f +0000000464 00000 n +0000002122 00000 n +0000000405 00000 n +0000000276 00000 n +0000000015 00000 n +0000000257 00000 n +0000000528 00000 n +0000000569 00000 n +0000000598 00000 n +trailer +<< /Size 10 /Root 1 0 R /Info 2 0 R +/ID [<33FAFB8CEAEE9DBD080319A9DEBAF35A><33FAFB8CEAEE9DBD080319A9DEBAF35A>] +>> +startxref +2352 +%%EOF
--- a/minimum_bisection/tikzpictures.tex Thu Jun 12 13:45:56 2014 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,101 +0,0 @@ -\pgfdeclarelayer{background} -\pgfdeclarelayer{demand} -\pgfdeclarelayer{marked} -\pgfdeclarelayer{foreground} -\pgfsetlayers{background,demand,marked,main,foreground} - -\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 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{tree edge} = [marked edge, tumgreen] -\tikzstyle{flow capacity} = [node on edge] -\tikzstyle{flow demand} = [node on edge, text=tumred] - -\tikzstyle{highlight} = [draw=tumorange, very thick, rounded corners] - -\newcommand{\tikzmark}[1]{\tikz[overlay,remember picture,baseline] \node [anchor=base] (#1) {};} - -\newcommand{\flownodes}{% - \pgfmathsetseed{42} - \def\jiggliness{0.2} - \def\jiggle{++ (rand * \jiggliness, rand * \jiggliness)} - - \path[use as bounding box] (-4, 2.7) rectangle (3.5,6.15); - - \foreach \pos/\name in { - % {(0,1)/a}, - {(-0.5,2.75)/b}, - {(0.5,3.25)/c}, - {(0.75,4)/d}, - {(-0.5,4.5)/e}, - {(-1.25,3.75)/f}, - {(1.5,4.75)/g}, - {(0,5.5)/h}, - {(2.5,5.5)/i}, - {(3.5,3.5)/j}, - {(2.25,4)/k}, - {(-2,6)/l}, - {(-2.5,5)/m}, - {(-4,5)/n}} - \draw \pos\jiggle node[flow node] (\name) {}; - % \draw \pos\jiggle node[flow node, label={\name}, font=\footnotesize] (\name) {}; -} -\newcommand{\flowedges}[1][]{% - \foreach \source/\dest in { - % {a/b}, {a/n}, {a/j}, - {n/b}, {b/j}, {f/b}, {c/b}, - {c/d}, {e/d}, {e/f}, {g/i}, - {h/e}, {h/i}, {i/j}, {k/j}, - {l/h}, {l/m}, {n/m}, - {c/k}, {k/i}, {g/d}, {m/e}, {n/l}, - {m/f}, {f/c}, {d/k}, {e/g}, {c/e}} - \draw[flow edge, #1] (\source) -- (\dest); -} -\newcommand{\flowcapacities}[1][]{% - \foreach \source/\dest/\capacity in { - % {a/b}, {a/n}, {a/j}, - {n/b/2}, {b/j/10}, {c/b/3}, {f/b/4}, - {c/d/4}, {e/d/2}, {e/f/4}, {g/i/2}, - {h/e/1}, {h/i/2}, {i/j/6}, {k/j/4}, - {l/h/3}, {l/m/4}, {n/m/5}, - {c/k/4}, {k/i/3}, {g/d/1}, {m/e/4}, {n/l/6}, - {m/f/1}, {f/c/2}, {d/k/4}, {e/g/1}, {c/e/5}} - \path (\source) -- node[flow capacity, #1]{\capacity} (\dest); -} -\newcommand{\flowdemands}{% - \begin{pgfonlayer}{demand} - \foreach \source/\dest/\demand/\pos/\bendage in { - {n/j/10/0.2/right}, - {h/j/8/0.2/left}, - {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); - \end{pgfonlayer} -} -\newcommand{\flowtreeedges}[1][]{% - \begin{pgfonlayer}{marked} - \foreach \source/ \dest in { - % {a/b}, - {c/b}, - {c/d}, {e/d}, {e/f}, {g/i}, - {m/e}, {d/k}, {i/j}, {k/j}, - {h/i}, {l/m}, {n/m}} - \draw [tree edge, #1] (\source.center) -- (\dest.center); - \end{pgfonlayer} -} -\newcommand{\flowtreeedgestwo}[1][]{% - \begin{pgfonlayer}{marked} - \foreach \source/ \dest in { - {n/l}, {l/h}, {h/i}, {i/g}, {i/j}, - {j/k}, {g/d}, {d/c}, {g/e}, {c/f}, - {f/m}, {f/b}} - \draw[tree edge, #1] (\source.center) -- (\dest.center); - \end{pgfonlayer} -}