latex: minimum_bisection/presentation/presentation.tex annotate

annotate minimum_bisection/presentation/presentation.tex @ 168:cc6bb3ca79fb default tip

6/4 is not 2

author	Markus Kaiser <markus.kaiser@in.tum.de>
date	Fri, 28 Nov 2014 01:41:50 +0100
parents	46887cff614e
children

rev	line source
124 e852e2a62ce4 presentation framework Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	1 \input{preamble.tex}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	2 \input{tikzpictures.tex}
124 e852e2a62ce4 presentation framework Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	3
e852e2a62ce4 presentation framework Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	4 \title{Oblivious Routing and Minimum Bisection}
136 1709ab3c1fcd fix subtitle; propagate renaming of tree metric Markus Kaiser <markus.kaiser@in.tum.de> parents: 135 diff changeset	5 \subtitle{Seminar: Approximation Algorithms}
124 e852e2a62ce4 presentation framework Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	6 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
141 b0f1f2800dce typo; correct date Markus Kaiser <markus.kaiser@in.tum.de> parents: 140 diff changeset	7 \date{June 3, 2014}
124 e852e2a62ce4 presentation framework Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	8
e852e2a62ce4 presentation framework Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	9 \begin{document}
e852e2a62ce4 presentation framework Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	10 \begin{frame}
e852e2a62ce4 presentation framework Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	11 \titlepage
e852e2a62ce4 presentation framework Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	12 \end{frame}
e852e2a62ce4 presentation framework Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	13
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	14 \begin{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	15 \frametitle{Flow Problems}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	16 \begin{problem}[Single Commodity Flow]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	17 Given
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	18 \begin{itemize}[<+->]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	19 \item An (un)directed Graph $G = (V, E)$
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	20 \item A \structure{capacity function} $c : E \to \R^+$
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	21 \item A source $s$ and a target $t$
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	22 \end{itemize}
131 349d3e5b7973 fix minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 130 diff changeset	23 \uncover<4->{Calculate a maximum possible \structure{flow} $f : E \to \R^+$ through $G$.}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	24 \end{problem}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	25
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	26 \centering
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	27 \begin{tikzpicture}[flow graph]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	28 \flownodes
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	29 \flowedges[directed]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	30 \only<2->{\flowcapacities}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	31
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	32 \draw<3->
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	33 (n.south) node[below] {\structure{s}}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	34 (j.south) node[below] {\structure{t}};
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	35 \end{tikzpicture}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	36 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	37
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	38 \begin{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	39 \frametitle{Flow Problems}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	40
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	41 \begin{problem}[Multi Commodity Flow]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	42 Given
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	43 \begin{itemize}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	44 \item An undirected Graph $G = (V, E)$
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	45 \item A capacity function $c : E \to \R^+$
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	46 \item<2-> A \structure{demand function} $d : V^2 \to \R^+$
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	47 \end{itemize}
131 349d3e5b7973 fix minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 130 diff changeset	48 \uncover<3->{Calculate a flow $f$ with least \structure{congestion $\rho = \max_{e \in E}\frac{f_e}{c_e}$}.}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	49 \end{problem}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	50
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	51 \centering
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	52 \begin{tikzpicture}[flow graph]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	53 \flownodes
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	54 \flowedges
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	55 \flowcapacities
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	56 \only<2->{\flowdemands}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	57 \end{tikzpicture}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	58 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	59
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	60 \begin{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	61 \frametitle{Oblivious Routing}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	62
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	63 \begin{problem}[Oblivious Routing]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	64 Given
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	65 \begin{itemize}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	66 \item An undirected Graph $G = (V, E)$
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	67 \item A capacity function $c : E \to \R^+$
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	68 \end{itemize}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	69 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.
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	70 \end{problem}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	71
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	72 \centering
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	73 \begin{tikzpicture}[flow graph]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	74 \flownodes
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	75 \flowedges
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	76 \flowcapacities
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	77
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	78 \draw<2->
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	79 (n.south) node[below] {\structure{u}}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	80 (j.south) node[below] {\structure{v}};
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	81
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	82 \only<3-> {
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	83 \begin{pgfonlayer}{marked}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	84 \draw[marked edge, tumgreen]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	85 (n.center) edge (l.center)
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	86 (l.center) edge (h.center)
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	87 (h.center) edge (i.center)
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	88 (i.center) edge (j.center);
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	89
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	90 \draw[marked edge, tumblue]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	91 (n.center) edge (m.center)
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	92 (m.center) edge (e.center)
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	93 (e.center) edge (c.center)
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	94 (c.center) edge (k.center)
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	95 (k.center) edge (j.center);
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	96
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	97 \draw[marked edge, tumred]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	98 (n.center) edge (b.center)
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	99 (b.center) edge (j.center);
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	100 \end{pgfonlayer}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	101
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	102 \path[font=\Large]
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	103 (n)
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	104 +(-0.5, 0.5) node[tumgreen] {$\frac{1}{4}$}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	105 +(-0.5, 0) node[tumblue] {$\frac{1}{2}$}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	106 +(-0.5, -0.5) node[tumred] {$\frac{1}{4}$};
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	107 }
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	108 \end{tikzpicture}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	109 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	110
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	111 \begin{frame}
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	112 \frametitle{Routing with a Spanning Tree}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	113
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	114 \begin{itemize}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	115 \item Choose any \structure{spanning tree $T$} of $G$
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	116 \item Routing along its unique paths is a feasible solution
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	117 \end{itemize}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	118
141 b0f1f2800dce typo; correct date Markus Kaiser <markus.kaiser@in.tum.de> parents: 140 diff changeset	119 \vfill
b0f1f2800dce typo; correct date Markus Kaiser <markus.kaiser@in.tum.de> parents: 140 diff changeset	120
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	121 \centering
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	122 \begin{tikzpicture}[flow graph]
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	123 \flownodes
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	124 \flowedges
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	125 \flowtreeedges
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	126
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	127 \only<2-> {
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	128 \draw
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	129 (l) node[above right] {\structure{u}}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	130 (i) node[above right] {\structure{v}};
133 b6150ddbcc3d move demand edges to demand layer Markus Kaiser <markus.kaiser@in.tum.de> parents: 132 diff changeset	131 \begin{pgfonlayer}{demand}
b6150ddbcc3d move demand edges to demand layer Markus Kaiser <markus.kaiser@in.tum.de> parents: 132 diff changeset	132 \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i);
b6150ddbcc3d move demand edges to demand layer Markus Kaiser <markus.kaiser@in.tum.de> parents: 132 diff changeset	133 \end{pgfonlayer}
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	134 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	135
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	136 \only<3-> {
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	137 \begin{pgfonlayer}{marked}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	138 \foreach \source/ \dest in {l/m,m/e,e/d,d/k,k/j,j/i}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	139 \draw[tree edge, tumred] (\source.center) edge (\dest.center);
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	140 \end{pgfonlayer}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	141 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	142
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	143 \only<4-> {
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	144 \flowcapacities
134 782316b52e1a fix displaystyle of fractions; choose randomly from [-1, 1] Markus Kaiser <markus.kaiser@in.tum.de> parents: 133 diff changeset	145 \node[below=0 of b] {\structure{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{10}{2} = 5$}};
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	146 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	147 \end{tikzpicture}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	148 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	149
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	150 \begin{frame}
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	151 \frametitle{Tree Splits}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	152
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	153 \begin{itemize}
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	154 \item Removing one edge $e_T$ from a ST creates a \structure{node partition $S(e_T)$}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	155 \item Every such partition has a \structure{capacity $C(e_T)$}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	156 \item And a \structure{demand $D(e_T)$}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	157 \end{itemize}
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	158 \begin{align}
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	159 C(e_T) &= \sum_{\substack{u \in S(e_T), \\ v \not\in S(e_T)}} c_{uv} &
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	160 D(e_T) &= \sum_{\substack{u \in S(e_T), \\ v \not\in S(e_T)}} c_{uv}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	161 \end{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	162
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	163 \centering
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	164 \begin{tikzpicture}[flow graph]
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	165 \flownodes
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	166 \flowedges
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	167 \flowtreeedges
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	168
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	169 \only<2-> {
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	170 \begin{pgfonlayer}{marked}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	171 \draw[tree edge, tumred] (m.center) edge (e.center);
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	172 \end{pgfonlayer}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	173
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	174 \begin{pgfonlayer}{background}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	175 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=3pt] (el) {};
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	176 \end{pgfonlayer}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	177
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	178 \path (el)
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	179 ++ (200:1.5)
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	180 ++ (0, -0.5) coordinate (label);
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	181 \node[below=0 of label] {\structure{$S(\alert{e_T})$}};
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	182 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	183
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	184 \only<3> {
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	185 \flowcapacities
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	186
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	187 \begin{pgfonlayer}{marked}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	188 \foreach \source/ \dest in {l/h,m/e,m/f,n/b}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	189 \draw[tree edge, tumorange] (\source.center) edge (\dest.center);
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	190 \end{pgfonlayer}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	191 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	192
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	193 \only<3-> {
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	194 \node[below=0.5 of label] {$C(e_T) = 10$};
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	195 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	196
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	197 \only<4-> {
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	198 \flowdemands
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	199
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	200 \begin{pgfonlayer}{demand}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	201 \foreach \source/\dest/\demand/\pos/\bendage in {
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	202 {n/j/10/0.2/right},
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	203 {n/h/12/0.7/left},
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	204 {k/m/5/0.8/right}}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	205 \draw[demand edge, bend \bendage=15, tumorange] (\source) edge node[flow demand, text=tumorange, pos=\pos]{\demand} (\dest);
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	206 \end{pgfonlayer}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	207
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	208 \node[below=1 of label] {$D(e_T) = 27$};
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	209 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	210 \end{tikzpicture}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	211 \end{frame}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	212
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	213 \begin{frame}
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	214 \frametitle{Optimal Solution}
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	215
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	216 \begin{lemma}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	217 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}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	218 \begin{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	219 \rho_e \geq \frac{D(e_T)}{C(e_T)}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	220 \end{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	221 And therefore the \structure{optimal solution $\rho^\ast$} can be no better.
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	222 \end{lemma}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	223
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	224 \vfill
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	225 \pause
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	226
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	227 \begin{itemize}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	228 \item Suppose we find a tree such that for some $\alpha$
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	229 \begin{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	230 \forall e_T \in E_T.\quad c_{e_T} \geq \frac{1}{\alpha} C(e_T)
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	231 \end{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	232 \item Then we have
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	233 \begin{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	234 \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}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	235 \end{align}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	236 \end{itemize}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	237 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	238
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	239 \begin{frame}
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	240 \frametitle{Routing with multiple Spanning Trees}
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	241
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	242 \begin{itemize}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	243 \item Choose a \structure{set of spanning trees $\left\{ T_i \right\}$} of $G$
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	244 \item And a \structure{convex combination $\lambda$} with $\sum_i \lambda_i = 1$, $\lambda \geq 0$
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	245 \item Routing is now split according to this combination. For $e \in E$
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	246 \begin{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	247 f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	248 \end{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	249 \end{itemize}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	250
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	251 \vfill
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	252
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	253 \centering
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	254 \begin{tikzpicture}[flow graph]
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	255 \flownodes
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	256 \flowedges
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	257
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	258 \draw
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	259 (l) node[above right] {\structure{u}}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	260 (i) node[above right] {\structure{v}};
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	261
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	262 \path
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	263 (n)
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	264 ++ (-1, -0.5) coordinate (label);
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	265
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	266 \only<2> {
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	267 \flowtreeedges
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	268 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	269
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	270 \only<2-> {
134 782316b52e1a fix displaystyle of fractions; choose randomly from [-1, 1] Markus Kaiser <markus.kaiser@in.tum.de> parents: 133 diff changeset	271 \node[tumgreen, below=0 of label, anchor=west] {$\displaystyle\lambda_1 = \frac{1}{2}$};
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	272 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	273
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	274 \only<3> {
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	275 \flowtreeedgestwo[tumorange]
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	276 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	277
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	278 \only<3-> {
134 782316b52e1a fix displaystyle of fractions; choose randomly from [-1, 1] Markus Kaiser <markus.kaiser@in.tum.de> parents: 133 diff changeset	279 \node[tumorange, below=0.5 of label, anchor=west] {$\displaystyle\lambda_2 = \frac{1}{2}$};
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	280 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	281
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	282 \only<4-> {
133 b6150ddbcc3d move demand edges to demand layer Markus Kaiser <markus.kaiser@in.tum.de> parents: 132 diff changeset	283 \begin{pgfonlayer}{demand}
b6150ddbcc3d move demand edges to demand layer Markus Kaiser <markus.kaiser@in.tum.de> parents: 132 diff changeset	284 \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i);
b6150ddbcc3d move demand edges to demand layer Markus Kaiser <markus.kaiser@in.tum.de> parents: 132 diff changeset	285 \end{pgfonlayer}
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	286
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	287 \begin{pgfonlayer}{marked}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	288 \foreach \source/ \dest in {l/m,m/e,e/d,d/k,k/j,j/i}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	289 \draw[tree edge, tumgreen] (\source.center) edge (\dest.center);
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	290 \end{pgfonlayer}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	291
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	292 \begin{pgfonlayer}{marked}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	293 \foreach \source/ \dest in {l/h,h/i}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	294 \draw[tree edge, tumorange] (\source.center) edge (\dest.center);
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	295 \end{pgfonlayer}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	296 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	297
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	298 \only<5-> {
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	299 \flowcapacities
134 782316b52e1a fix displaystyle of fractions; choose randomly from [-1, 1] Markus Kaiser <markus.kaiser@in.tum.de> parents: 133 diff changeset	300 \node[below=1 of label, anchor=west] {\structure{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{5}{2} = 2.5$}};
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	301 }
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	302 \end{tikzpicture}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	303 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	304
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	305 \begin{frame}
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	306 \frametitle{Routing with multiple Spanning Trees}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	307
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	308 \begin{itemize}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	309 % \item Remember that the total flow on edge $e \in E$ is
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	310 % \begin{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	311 % f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	312 % \end{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	313 \item Suppose we now find a \structure{set of trees} such that for some $\alpha$
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	314 \begin{align}
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	315 \forall e \in E.\quad c_{e} \geq \frac{1}{\alpha} \sum_{\substack{i:\\e \in T_i}} \lambda_i C_i(e)
126 b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	316 \end{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	317 \vfill
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	318 \item Then we have
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	319 \begingroup
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	320 \addtolength{\jot}{.5em}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	321 \begin{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	322 \structure{\rho} &= \hphantom{\alpha}\max_{e} \frac{f(e)}{c_{e}} \\
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	323 &= \hphantom{\alpha}\max_{e} \frac{\sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)}{c_e} \\
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	324 &\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)} \\
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	325 &\leq \alpha \max_{e} \max_{i} \frac{D_i(e)}{C_i(e)} \leq \structure{\alpha \rho^\ast}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	326 \end{align}
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	327 \endgroup
b948ace51db7 more frames on the way to the linear program Markus Kaiser <markus.kaiser@in.tum.de> parents: 125 diff changeset	328 \end{itemize}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	329 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	330
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	331 \begin{frame}
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	332 \frametitle{Pathtrees}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	333
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	334 \begin{itemize}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	335 \item Identify every edge in a tree with a \structure{path} in $G$
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	336 \item These paths can \structure{overlap}
131 349d3e5b7973 fix minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 130 diff changeset	337 \item For tree $T$ we get a mapping $P_T : E_T \to E^+$
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	338 \end{itemize}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	339
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	340 \vfill
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	341
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	342 \centering
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	343 \begin{tikzpicture}[flow graph]
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	344 \flownodes
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	345 \flowedges
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	346 \flowtreeedges
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	347 \flowcapacities
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	348
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	349 \draw
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	350 (e) node[above right] {\structure{a}}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	351 (d) node[above=0.1] {\structure{b}};
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	352
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	353 \only<2-> {
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	354 \begin{pgfonlayer}{marked}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	355 \draw[tree edge, line width=4pt, white] (e.center) edge (d.center);
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	356 \draw[tree edge, densely dashed, tumgreen!80] (e.center) edge (d.center);
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	357
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	358 \foreach \source/\dest in {e/c,c/d}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	359 \draw[tree edge, tumblue!80] (\source.center) edge (\dest.center);
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	360 \end{pgfonlayer}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	361 }
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	362 \end{tikzpicture}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	363 \end{frame}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	364
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	365 \begin{frame}
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	366 \frametitle{Routing with multiple Pathtrees}
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	367
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	368 \begin{itemize}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	369 \item Choose a \structure{set of pathtrees $\left\{ T_i \right\}$} of $G$ with \structure{combination $\lambda$}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	370 \item Now route along the paths identified with edges. For $e \in E$
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	371 \begin{align}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	372 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})
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	373 \end{align}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	374 \end{itemize}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	375
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	376 \vfill
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	377
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	378 \centering
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	379 \begin{tikzpicture}[flow graph]
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	380 \flownodes
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	381 \flowedges
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	382
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	383 \draw
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	384 (l) node[above right] {\structure{u}}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	385 (i) node[above right] {\structure{v}};
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	386
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	387 \path
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	388 (n)
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	389 ++ (-1, -0.5) coordinate (label);
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	390
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	391 \only<2> {
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	392 \flowtreeedges
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	393 }
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	394
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	395 \only<2-> {
134 782316b52e1a fix displaystyle of fractions; choose randomly from [-1, 1] Markus Kaiser <markus.kaiser@in.tum.de> parents: 133 diff changeset	396 \node[tumgreen, below=0 of label, anchor=west] {$\displaystyle\lambda_1 = \frac{2}{3}$};
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	397 }
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	398
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	399 \only<3> {
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	400 \flowtreeedgestwo[tumorange]
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	401 }
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	402
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	403 \only<3-> {
134 782316b52e1a fix displaystyle of fractions; choose randomly from [-1, 1] Markus Kaiser <markus.kaiser@in.tum.de> parents: 133 diff changeset	404 \node[tumorange, below=0.5 of label, anchor=west] {$\displaystyle\lambda_2 = \frac{1}{3}$};
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	405 }
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	406
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	407 \only<4-> {
131 349d3e5b7973 fix minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 130 diff changeset	408 \begin{pgfonlayer}{demand}
349d3e5b7973 fix minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 130 diff changeset	409 \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{9} (i);
349d3e5b7973 fix minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 130 diff changeset	410 \end{pgfonlayer}
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	411
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	412 \begin{pgfonlayer}{marked}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	413 \foreach \source/ \dest in {l/m,m/e,d/k,k/j,j/i}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	414 \draw[tree edge, tumgreen] (\source.center) edge (\dest.center);
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	415 \end{pgfonlayer}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	416
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	417 \begin{pgfonlayer}{marked}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	418 \draw[tree edge, line width=4pt, white] (e.center) edge (d.center);
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	419 \draw[tree edge, densely dashed, tumgreen!80] (e.center) edge (d.center);
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	420
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	421 \foreach \source/\dest in {e/c,c/d}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	422 \draw[tree edge, tumblue!80] (\source.center) edge (\dest.center);
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	423 \end{pgfonlayer}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	424
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	425 \begin{pgfonlayer}{marked}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	426 \foreach \source/ \dest in {l/h,h/i}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	427 \draw[tree edge, tumorange] (\source.center) edge (\dest.center);
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	428 \end{pgfonlayer}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	429 }
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	430
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	431 \only<5-> {
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	432 \flowcapacities
168 cc6bb3ca79fb 6/4 is not 2 Markus Kaiser <markus.kaiser@in.tum.de> parents: 145 diff changeset	433 \node[below=1 of label, anchor=west] {\structure{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{6}{4} = 1.5$}};
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	434 }
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	435 \end{tikzpicture}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	436 \end{frame}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	437
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	438 \begin{frame}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	439 \frametitle{Routing with multiple pathtrees}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	440
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	441 \begin{itemize}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	442 \item Again suppose we now find a \structure{set of trees} such that for some $\alpha$
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	443 \begin{align}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	444 \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})
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	445 \end{align}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	446 \item Then we have
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	447 \begingroup
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	448 \addtolength{\jot}{.5em}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	449 \begin{align}
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	450 \rho &= \hphantom{\alpha}\max_{\structure{e}} \frac{f(\structure{e})}{c_{\structure{e}}} \\
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	451 &\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})} \\
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	452 &\leq \alpha \max_{\structure{e}} \max_{i} \frac{D_i(\structure{e})}{C_i(\structure{e})} \leq \alpha \rho^\ast
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	453 \end{align}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	454 \endgroup
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	455 \end{itemize}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	456
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	457 \vfill
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	458
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	459 \only<2> {
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	460 \begin{center}
131 349d3e5b7973 fix minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 130 diff changeset	461 How do we find such a set of trees? How large is $\alpha$?
127 c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	462 \end{center}
c213b1f538ed captain! we have reached the primal program! Markus Kaiser <markus.kaiser@in.tum.de> parents: 126 diff changeset	463 }
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	464 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	465
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	466 \begin{frame}
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	467 \frametitle{Primal program}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	468
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	469 \begin{block}{Primal Program}
141 b0f1f2800dce typo; correct date Markus Kaiser <markus.kaiser@in.tum.de> parents: 140 diff changeset	470 Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.\\
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	471 We want to find the best trees with smallest $\alpha$.
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	472 \begin{alignat}{3}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	473 \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	474 \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 \\
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	475 && \sum_{i \in \Ih} \structure{\lambda_i} &= 1 \\
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	476 && \structure{\lambda} &\geq 0
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	477 \end{alignat}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	478 \end{block}
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	479
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	480 \vfill
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	481
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	482 \begin{center}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	483 We want to show that $\alpha \in \Oh(\log n)$
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	484 \end{center}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	485 \end{frame}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	486
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	487 \begin{frame}
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	488 \frametitle{Dual Program}
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	489
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	490 \begin{block}{Dual Program}
141 b0f1f2800dce typo; correct date Markus Kaiser <markus.kaiser@in.tum.de> parents: 140 diff changeset	491 Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	492 \begin{alignat}{3}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	493 \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ %
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	494 \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	495 && \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 \\
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	496 && \structure{\Ell} &\geq 0
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	497 \end{alignat}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	498 \end{block}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	499
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	500 \vfill
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	501
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	502 \begin{center}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	503 If $z \in \Oh(\log n)$ then $\alpha \in \Oh(\log n)$ by strong duality
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	504 \end{center}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	505 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	506
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	507 \begin{frame}
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	508 \frametitle{Solution of the Dual Program}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	509
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	510 \begin{block}{Dual Program}
141 b0f1f2800dce typo; correct date Markus Kaiser <markus.kaiser@in.tum.de> parents: 140 diff changeset	511 Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	512 \begin{alignat}{3}
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	513 \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ %
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	514 \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	515 \only<-2>{
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	516 && \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 \\
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	517 }
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	518 \only<3-4>{
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	519 && \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 \\
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	520 }
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	521 \only<5->{
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	522 && \structure{z} & \leq \min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)\\
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	523 }
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	524 && \structure{\Ell} &\geq 0
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	525 \end{alignat}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	526 \end{block}
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	527
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	528 \vfill
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	529
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	530 \begin{itemize}
132 66e22e40b383 add missing structure; remove dummy frame Markus Kaiser <markus.kaiser@in.tum.de> parents: 131 diff changeset	531 \item We interpret the $\structure{\ell_{uv}}$ as edge lengths in $G$
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	532 \item They define a \structure{shortest path metric $d_{\structure{\ell}}(u, v)$}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	533 \item For an edge $e = (x, y)$ we write $d_{\structure{\ell}}(e) \defeq d_{\structure{\ell}}(x, y)$
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	534 \end{itemize}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	535 \begin{tikzpicture}[remember picture, overlay]
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	536 \only<2> {%
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	537 \node[fit=(a)(b), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below:{$\geq d_{\structure{\ell}}(e_T)$}}] {};
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	538 }
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	539 \only<4> {%
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	540 \node[fit=(c)(d), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below right:{$\geq \min_{i \in \Ih} \cdots$}}] {};
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	541 }
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	542 \end{tikzpicture}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	543 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	544
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	545 \begin{frame}
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	546 \frametitle{Solution of the Dual Program}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	547
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	548 \begin{block}{Dual Program}
141 b0f1f2800dce typo; correct date Markus Kaiser <markus.kaiser@in.tum.de> parents: 140 diff changeset	549 Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	550 \only<1-2>{%
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	551 \begin{alignat}{3}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	552 \max_{\structure{\Ell}} \quad & \mathrlap{\min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)}\\
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	553 \st \quad && \tikzmark{a}\sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1\tikzmark{b} \\
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	554 && \structure{\Ell} &\geq 0
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	555 \end{alignat}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	556 \vspace{-1em}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	557 }
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	558 \only<3>{%
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	559 \begin{alignat}{3}
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	560 \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}}}\\
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	561 \st \quad & \structure{\Ell} \geq 0
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	562 \end{alignat}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	563 }
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	564 \end{block}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	565
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	566 \vfill
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	567
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	568 \uncover<2-3>{
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	569 \begin{itemize}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	570 \item Now suppose
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	571 \begin{align}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	572 \sum_{u, v \in V} c_{uv} \ell_{uv} = \beta > 0
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	573 \end{align}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	574 \item If we scale every length by $\frac{1}{\beta}$ our solution will change by $\frac{1}{\beta}$
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	575 \end{itemize}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	576 }
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	577 \begin{tikzpicture}[remember picture, overlay]
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	578 \only<2>{
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	579 \node[fit=(a)(b), highlight, minimum height=2.5em, inner sep=-3pt] {};
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	580 }
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	581 \end{tikzpicture}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	582 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	583
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	584 \begin{frame}
138 243db45547c5 typo Markus Kaiser <markus.kaiser@in.tum.de> parents: 136 diff changeset	585 \frametitle{Tree Metric}
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	586
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	587 \begin{theorem}[Tree Metric]
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	588 For our metric $d_\ell$ there exists a \structure{tree metric $(V, M)$} with
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	589 \begingroup
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	590 \addtolength{\jot}{.5em}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	591 \begin{alignat}{2}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	592 d_\ell(u, v) &\leq M_{uv} & \forall u, v \in V\\
142 c7e07d48caee fix tree metrics inequality; give nodes a name in bisection argument Markus Kaiser <markus.kaiser@in.tum.de> parents: 141 diff changeset	593 \sum_{u, v \in V} c_{uv} M_{uv} &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v)
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	594 \end{alignat}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	595 \endgroup
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	596 \end{theorem}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	597
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	598 \vfill
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	599
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	600 \centering
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	601 \begin{tikzpicture}[grow=down, level distance = 25]
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	602 \begin{scope}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	603 \tikzstyle{every node} = [draw, flow node]
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	604 \tikzstyle{edge from parent} = [draw, edge]
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	605
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	606 \tikzstyle{level 1} = [sibling distance = 100]
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	607 \tikzstyle{level 2} = [sibling distance = 50]
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	608 \tikzstyle{level 3} = [sibling distance = 30]
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	609 \node[label=above:$z$] (z) {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	610 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	611 node[label=above left:$y$] (y) {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	612 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	613 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	614 node[label=above left:$x$] (x) {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	615 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	616 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	617 node[label=below left:$\structure{u}$] (u) {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	618 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	619 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	620 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	621 node {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	622 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	623 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	624 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	625 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	626 node {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	627 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	628 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	629 node {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	630 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	631 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	632 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	633 node {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	634 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	635 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	636 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	637 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	638 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	639 node[label=above right:$\structure{v}$] (v) {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	640 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	641 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	642 node {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	643 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	644 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	645 node {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	646 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	647 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	648 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	649 node {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	650 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	651 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	652 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	653 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	654 node {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	655 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	656 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	657 node {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	658 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	659 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	660 child {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	661 node {}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	662 edge from parent
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	663 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	664 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	665 };
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	666 \end{scope}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	667
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	668 \begin{pgfonlayer}{marked}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	669 \foreach \source/\dest in {u/x,x/y,y/z,z/v}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	670 \draw [tree edge, tumred] (\source.center) -- (\dest.center);
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	671 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	672
136 1709ab3c1fcd fix subtitle; propagate renaming of tree metric Markus Kaiser <markus.kaiser@in.tum.de> parents: 135 diff changeset	673 \node at (0, -3.5) {$M_{uv} = M_{ux} + M_{xy} + M_{yz} + M_{zv}$};
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	674 \end{tikzpicture}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	675 \end{frame}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	676
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	677 \begin{frame}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	678 \frametitle{Sum over all capacities}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	679
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	680 \begin{lemma}[]
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	681 Let $T$ be a spanning tree and $(V, M)$ a tree metric of $G = (V, E)$. Then
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	682 \begin{align}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	683 \sum_{(x, y) \in E_T} C(x, y) M_{xy} = \sum_{(u, v) \in E} c_{uv} M_{uv}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	684 \end{align}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	685 \end{lemma}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	686
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	687 \vfill
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	688
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	689 \centering
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	690 \begin{tikzpicture}[flow graph]
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	691 \flownodes
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	692 \flowedges
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	693 \flowtreeedges
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	694
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	695 \draw
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	696 (n) node[above=0.1] {\structure{u}}
131 349d3e5b7973 fix minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 130 diff changeset	697 (m) node[below=0.05] {a}
349d3e5b7973 fix minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 130 diff changeset	698 (e) node[below=0.05] {b}
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	699 (d) node[above=0.1] {c}
131 349d3e5b7973 fix minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 130 diff changeset	700 (c) node[below=0.05] {d}
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	701 (b) node[above=0.1] {\structure{v}};
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	702
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	703 \path
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	704 (n) -- node[node on edge] {$c_{uv}$} (b);
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	705
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	706 \begin{pgfonlayer}{marked}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	707 \draw[tree edge, tumorange] (n.center) edge (b.center);
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	708 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	709
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	710 \only<2> {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	711 \begin{pgfonlayer}{marked}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	712 \draw[tree edge, tumred] (n.center) edge (m.center);
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	713 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	714
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	715 \begin{pgfonlayer}{background}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	716 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(n), inner sep=15pt] (el) {};
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	717 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	718 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	719 \only<3> {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	720 \begin{pgfonlayer}{marked}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	721 \draw[tree edge, tumred] (m.center) edge (e.center);
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	722 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	723
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	724 \begin{pgfonlayer}{background}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	725 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=3pt] (el) {};
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	726 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	727 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	728 \only<4> {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	729 \begin{pgfonlayer}{marked}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	730 \draw[tree edge, tumred] (e.center) edge (d.center);
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	731 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	732
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	733 \begin{pgfonlayer}{background}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	734 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m)(e)(f), inner sep=3pt] (el) {};
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	735 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	736 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	737 \only<5> {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	738 \begin{pgfonlayer}{marked}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	739 \draw[tree edge, tumred] (d.center) edge (c.center);
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	740 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	741
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	742 \begin{pgfonlayer}{background}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	743 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=-10, fit=(c)(b), inner sep=3pt] (el) {};
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	744 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	745 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	746 \only<6> {
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	747 \begin{pgfonlayer}{marked}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	748 \draw[tree edge, tumred] (c.center) edge (b.center);
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	749 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	750
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	751 \begin{pgfonlayer}{background}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	752 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(b), inner sep=15pt] (el) {};
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	753 \end{pgfonlayer}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	754 }
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	755 \end{tikzpicture}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	756 \end{frame}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	757
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	758 \begin{frame}
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	759 \frametitle{Value of the Dual Problem}
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	760
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	761 \begin{block}{Dual Program}
141 b0f1f2800dce typo; correct date Markus Kaiser <markus.kaiser@in.tum.de> parents: 140 diff changeset	762 Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	763 \begin{alignat}{3}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	764 \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}}}\\
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	765 \st \quad & \structure{\Ell} \geq 0
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	766 \end{alignat}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	767 \end{block}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	768
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	769 For any $\Ell$ we know that for the \structure{minimizing tree $T_i$} holds
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	770 \begin{align}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	771 \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} \\
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	772 &= \sum_{u, v \in V} c_{uv} M_{uv} \\
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	773 &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v) \\
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	774 &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} \ell_{uv} \\
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	775 \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)
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	776 \end{align}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	777 \end{frame}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	778
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	779 \begin{frame}
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	780 \frametitle{Value of the Primal Program}
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	781
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	782 \begin{block}{Primal Program}
141 b0f1f2800dce typo; correct date Markus Kaiser <markus.kaiser@in.tum.de> parents: 140 diff changeset	783 Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.\\
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	784 We want to find the best trees with smallest $\alpha$.
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	785 \begin{alignat}{3}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	786 \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	787 \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 \\
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	788 && \sum_{i \in \Ih} \structure{\lambda_i} &= 1 \\
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	789 && \structure{\lambda} &\geq 0
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	790 \end{alignat}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	791 \end{block}
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	792
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	793 \vfill
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	794
0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	795 \begin{itemize}
131 349d3e5b7973 fix minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 130 diff changeset	796 \item There is a $\structure{\lambda}$ such that $\structure{\alpha \in \Oh(\log n)}$
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	797 \item But why are polynomially many trees enough?
144 9fde0cffa295 you do not solve the LP Markus Kaiser <markus.kaiser@in.tum.de> parents: 143 diff changeset	798 \item This gives an \alert{$\Oh(\log n)$-approximation}
130 0924abe91f55 solve the dual problem Markus Kaiser <markus.kaiser@in.tum.de> parents: 129 diff changeset	799 \end{itemize}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	800 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	801
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	802 \begin{frame}
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	803 \frametitle{Minimum Bisection}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	804
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	805 \begin{problem}[Minimum Bisection]
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	806 Given
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	807 \begin{itemize}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	808 \item An undirected Graph $G = (V, E)$
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	809 \item A cost function $c : E \to \R^+$
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	810 \end{itemize}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	811 Find a set $S \subset V$ containing half the vertices with \structure{minimal split cost}.
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	812 \end{problem}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	813
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	814 \vfill
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	815
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	816 \centering
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	817 \begin{tikzpicture}[flow graph]
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	818 \flownodes
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	819 \flowedges
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	820 \flowcapacities
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	821
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	822 \only<2-> {
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	823 \begin{pgfonlayer}{background}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	824 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {};
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	825 \end{pgfonlayer}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	826
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	827 \path (el)
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	828 ++ (-30:2.3) node {\structure{$S$}};
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	829 }
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	830
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	831 \only<3-4> {
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	832 \begin{pgfonlayer}{marked}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	833 \foreach \source/\dest in {b/j,b/c,c/f,e/c,e/d,e/g,h/i}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	834 \draw [tree edge, tumorange] (\source.center) -- (\dest.center);
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	835 \end{pgfonlayer}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	836
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	837 \path (n)
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	838 ++ (-0.5, -1.5) node[tumorange, anchor=west] {\alt<3>{$\hphantom{c(}\delta(S)$}{$c(\delta(S)) = 25$}};
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	839 }
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	840 \end{tikzpicture}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	841 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	842
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	843 \begin{frame}
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	844 \frametitle{Approximation Algorithm}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	845
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	846 \begin{block}{Minimum Bisection Approximation}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	847 Given graph $G = (V, E)$ and cost function $c : E \to \R^+$.
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	848 \begin{enumerate}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	849 \item Interpret costs $c(e)$ as \structure{capacities}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	850 \item Solve oblivious routing on $G$, obtaining \structure{trees $T_i$}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	851 \item Find minimum \structure{tree bisections $X_i$} for all trees $T_i$
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	852 \item Choose the $X_i$ with \structure{lowest $c(\delta(X_i))$}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	853 \end{enumerate}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	854 \end{block}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	855
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	856 \vfill
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	857 \pause
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	858
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	859 We have to show
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	860 \begin{itemize}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	861 \item What the $X_i$ actually are
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	862 \item An \alert{$\Oh(\log n)$-approximation} guarantee
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	863 \item That we can find the $X_i$ in polynomial time
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	864 \end{itemize}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	865 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	866
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	867 \begin{frame}
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	868 \frametitle{Tree Bisections}
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	869
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	870 \begin{itemize}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	871 \item Given a spanning tree $T$ of $G$ with an edge $e_T \in E_T$
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	872 \item Define a new \structure{cost function $c_T$} using tree splits
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	873 \end{itemize}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	874 \begin{align}
140 586786c65297 remove minor errors Markus Kaiser <markus.kaiser@in.tum.de> parents: 139 diff changeset	875 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)
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	876 \end{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	877
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	878 \vfill
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	879
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	880 \centering
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	881 \begin{tikzpicture}[flow graph]
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	882 \flownodes
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	883 \flowedges
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	884 \flowtreeedges
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	885
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	886 \only<2-> {
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	887 \begin{pgfonlayer}{background}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	888 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {};
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	889 \end{pgfonlayer}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	890
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	891 \path (el)
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	892 ++ (-30:2.3) node {\structure{$S$}};
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	893 }
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	894
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	895 \only<3> {
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	896 \begin{pgfonlayer}{marked}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	897 \foreach \source/\dest in {b/c,e/d,h/i}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	898 \draw [tree edge, tumred] (\source.center) -- (\dest.center);
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	899 \end{pgfonlayer}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	900
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	901 \foreach \source/\dest/\name in {b/c/$e_3$,e/d/$e_2$,h/i/$e_1$}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	902 \path (\source) -- node[node on edge] {\name} (\dest);
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	903
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	904 \path (n)
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	905 ++ (-1, -1.5) node[tumred, anchor=west] {$\displaystyle c_T(\delta(S)) = \sum_{k=1}^3 C(e_k)$};
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	906 }
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	907 \end{tikzpicture}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	908 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	909
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	910 \begin{frame}
139 247f86a0ff6b Typos in Frametitles Markus Kaiser <markus.kaiser@in.tum.de> parents: 138 diff changeset	911 \frametitle{Tree Bisections}
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	912
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	913 \begin{lemma}[]
142 c7e07d48caee fix tree metrics inequality; give nodes a name in bisection argument Markus Kaiser <markus.kaiser@in.tum.de> parents: 141 diff changeset	914 For any spanning tree $T$ and any $S \subseteq V$ we have
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	915 \begin{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	916 c(\delta(S)) \leq c_T(\delta(S))
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	917 \end{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	918 \end{lemma}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	919
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	920 \vfill
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	921
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	922 \centering
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	923 \begin{tikzpicture}[flow graph]
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	924 \flownodes
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	925 \flowedges
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	926 \flowtreeedges
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	927
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	928 \begin{pgfonlayer}{background}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	929 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {};
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	930 \end{pgfonlayer}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	931
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	932 \path (el)
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	933 ++ (-30:2.3) node {\structure{$S$}};
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	934
142 c7e07d48caee fix tree metrics inequality; give nodes a name in bisection argument Markus Kaiser <markus.kaiser@in.tum.de> parents: 141 diff changeset	935 \draw
c7e07d48caee fix tree metrics inequality; give nodes a name in bisection argument Markus Kaiser <markus.kaiser@in.tum.de> parents: 141 diff changeset	936 (b) node[below=0.05] {\structure{u}}
c7e07d48caee fix tree metrics inequality; give nodes a name in bisection argument Markus Kaiser <markus.kaiser@in.tum.de> parents: 141 diff changeset	937 (j) node[below=0.05] {\structure{v}};
c7e07d48caee fix tree metrics inequality; give nodes a name in bisection argument Markus Kaiser <markus.kaiser@in.tum.de> parents: 141 diff changeset	938
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	939 \begin{pgfonlayer}{marked}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	940 \foreach \source/\dest in {b/j,f/c,e/c,e/g}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	941 \draw [tree edge, tumblue, dash pattern=on 7pt off 7pt] (\source.center) -- (\dest.center);
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	942
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	943 \foreach \source/\dest in {b/c,e/d,h/i}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	944 \draw [tree edge, tumred] (\source.center) -- (\dest.center);
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	945 \end{pgfonlayer}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	946
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	947 \foreach \source/\dest/\name in {b/c/$e_3$,e/d/$e_2$,h/i/$e_1$}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	948 \path (\source) -- node[node on edge] {\name} (\dest);
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	949 \end{tikzpicture}
129 1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	950 \end{frame}
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	951
1b2e38c66a67 dual conversion Markus Kaiser <markus.kaiser@in.tum.de> parents: 127 diff changeset	952 \begin{frame}
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	953 \frametitle{Tree Bisections}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	954
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	955 \begin{lemma}[]
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	956 Let $\left\{ T_i \right\}$ be a solution to the \structure{oblivious flow} problem on $G$.\\
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	957 Then for any $S \subseteq V$ we have
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	958 \begin{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	959 \sum_i \lambda_i c_{T_i}(\delta(S)) \leq \Oh(\log n) c(\delta(S))
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	960 \end{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	961 \end{lemma}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	962
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	963 \vfill
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	964
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	965 \begin{itemize}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	966 \only<1> {
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	967 \item Remember from the primal program that \structure{for all $u, v \in V$}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	968 \begin{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	969 \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}}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	970 \end{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	971 \item We sum up the inequalities for all $(u, v) \in \delta(S)$
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	972 }
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	973 \only<2> {
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	974 \item We sum up the inequalities for all $(u, v) \in \delta(S)$
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	975 \item This gives us
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	976 \begin{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	977 \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))
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	978 \end{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	979 \item We are done with the observation that
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	980 \begin{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	981 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)
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	982 \end{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	983 }
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	984 \end{itemize}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	985 \end{frame}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	986
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	987 \begin{frame}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	988 \frametitle{Approximation Algorithm}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	989
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	990 \begin{block}{Minimum Bisection Approximation}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	991 Given graph $G = (V, E)$ and cost function $c : E \to \R^+$.
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	992 \begin{enumerate}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	993 \item Interpret costs $c(e)$ as \structure{capacities}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	994 \item Solve oblivious routing on $G$, obtaining \structure{trees $T_i$}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	995 \item Find minimum \structure{tree bisections $X_i$} for all trees $T_i$
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	996 \item Choose the $X_i$ with \structure{lowest $c(\delta(X_i))$}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	997 \end{enumerate}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	998 \end{block}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	999
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	1000 \vfill
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	1001
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	1002 \begin{itemize}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	1003 \item Let now $X^*, X_i$ be the optimal solutions on $G$ and the $T_i$. Then
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	1004 \begin{align}
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	1005 \sum_i \lambda_i c(\delta(X_i)) &\leq \sum_i \lambda_i c_{T_i}(\delta(X_i)) \\
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	1006 &\leq \sum_i \lambda_i c_{T_i}(\delta(X^*)) \\
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	1007 &\leq \Oh(\log n) c(\delta(X^*))
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	1008 \end{align}
143 533cc8f9e627 add approximation-alert Markus Kaiser <markus.kaiser@in.tum.de> parents: 142 diff changeset	1009 \item This also holds for the \structure{best $X_i$}, giving an \alert{$\Oh(\log n)$-approximation}
135 c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	1010 \item How to find the $X_i$?
c0eb673db33e finish minimum bisection presentation Markus Kaiser <markus.kaiser@in.tum.de> parents: 134 diff changeset	1011 \end{itemize}
125 2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	1012 \end{frame}
2af28ac8a070 first few slides Markus Kaiser <markus.kaiser@in.tum.de> parents: 124 diff changeset	1013
124 e852e2a62ce4 presentation framework Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	1014 \end{document}

Mercurial > latex

annotate minimum_bisection/presentation/presentation.tex @ 168:cc6bb3ca79fb default tip