Mercurial > latex
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 | 1 \input{preamble.tex} |
125 | 2 \input{tikzpictures.tex} |
124 | 3 |
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 | 6 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} |
141 | 7 \date{June 3, 2014} |
124 | 8 |
9 \begin{document} | |
10 \begin{frame} | |
11 \titlepage | |
12 \end{frame} | |
13 | |
125 | 14 \begin{frame} |
15 \frametitle{Flow Problems} | |
16 \begin{problem}[Single Commodity Flow] | |
17 Given | |
18 \begin{itemize}[<+->] | |
19 \item An (un)directed Graph $G = (V, E)$ | |
20 \item A \structure{capacity function} $c : E \to \R^+$ | |
21 \item A source $s$ and a target $t$ | |
22 \end{itemize} | |
131 | 23 \uncover<4->{Calculate a maximum possible \structure{flow} $f : E \to \R^+$ through $G$.} |
125 | 24 \end{problem} |
25 | |
26 \centering | |
27 \begin{tikzpicture}[flow graph] | |
28 \flownodes | |
29 \flowedges[directed] | |
30 \only<2->{\flowcapacities} | |
31 | |
32 \draw<3-> | |
33 (n.south) node[below] {\structure{s}} | |
34 (j.south) node[below] {\structure{t}}; | |
35 \end{tikzpicture} | |
36 \end{frame} | |
37 | |
38 \begin{frame} | |
39 \frametitle{Flow Problems} | |
40 | |
41 \begin{problem}[Multi Commodity Flow] | |
42 Given | |
43 \begin{itemize} | |
44 \item An undirected Graph $G = (V, E)$ | |
45 \item A capacity function $c : E \to \R^+$ | |
46 \item<2-> A \structure{demand function} $d : V^2 \to \R^+$ | |
47 \end{itemize} | |
131 | 48 \uncover<3->{Calculate a flow $f$ with least \structure{congestion $\rho = \max_{e \in E}\frac{f_e}{c_e}$}.} |
125 | 49 \end{problem} |
50 | |
51 \centering | |
52 \begin{tikzpicture}[flow graph] | |
53 \flownodes | |
54 \flowedges | |
55 \flowcapacities | |
56 \only<2->{\flowdemands} | |
57 \end{tikzpicture} | |
58 \end{frame} | |
59 | |
60 \begin{frame} | |
61 \frametitle{Oblivious Routing} | |
62 | |
63 \begin{problem}[Oblivious Routing] | |
64 Given | |
65 \begin{itemize} | |
66 \item An undirected Graph $G = (V, E)$ | |
67 \item A capacity function $c : E \to \R^+$ | |
68 \end{itemize} | |
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. | |
70 \end{problem} | |
71 | |
72 \centering | |
73 \begin{tikzpicture}[flow graph] | |
74 \flownodes | |
75 \flowedges | |
76 \flowcapacities | |
77 | |
78 \draw<2-> | |
79 (n.south) node[below] {\structure{u}} | |
80 (j.south) node[below] {\structure{v}}; | |
81 | |
82 \only<3-> { | |
83 \begin{pgfonlayer}{marked} | |
84 \draw[marked edge, tumgreen] | |
85 (n.center) edge (l.center) | |
86 (l.center) edge (h.center) | |
87 (h.center) edge (i.center) | |
88 (i.center) edge (j.center); | |
89 | |
90 \draw[marked edge, tumblue] | |
91 (n.center) edge (m.center) | |
92 (m.center) edge (e.center) | |
93 (e.center) edge (c.center) | |
94 (c.center) edge (k.center) | |
95 (k.center) edge (j.center); | |
96 | |
97 \draw[marked edge, tumred] | |
98 (n.center) edge (b.center) | |
99 (b.center) edge (j.center); | |
100 \end{pgfonlayer} | |
101 | |
102 \path[font=\Large] | |
103 (n) | |
104 +(-0.5, 0.5) node[tumgreen] {$\frac{1}{4}$} | |
105 +(-0.5, 0) node[tumblue] {$\frac{1}{2}$} | |
106 +(-0.5, -0.5) node[tumred] {$\frac{1}{4}$}; | |
107 } | |
108 \end{tikzpicture} | |
109 \end{frame} | |
110 | |
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 | 119 \vfill |
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 | 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 | 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 | 148 \end{frame} |
149 | |
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 | 152 |
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 | 236 \end{itemize} |
237 \end{frame} | |
238 | |
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 | 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 | 303 \end{frame} |
304 | |
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 | 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 | 329 \end{frame} |
330 | |
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 | 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 | 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 | 408 \begin{pgfonlayer}{demand} |
409 \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{9} (i); | |
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 | 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 | 450 \rho &= \hphantom{\alpha}\max_{\structure{e}} \frac{f(\structure{e})}{c_{\structure{e}}} \\ |
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})} \\ | |
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 | 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 | 464 \end{frame} |
465 | |
466 \begin{frame} | |
129 | 467 \frametitle{Primal program} |
125 | 468 |
469 \begin{block}{Primal Program} | |
141 | 470 Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.\\ |
129 | 471 We want to find the best trees with smallest $\alpha$. |
125 | 472 \begin{alignat}{3} |
473 \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\ | |
129 | 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 \\ |
475 && \sum_{i \in \Ih} \structure{\lambda_i} &= 1 \\ | |
125 | 476 && \structure{\lambda} &\geq 0 |
477 \end{alignat} | |
478 \end{block} | |
129 | 479 |
480 \vfill | |
481 | |
482 \begin{center} | |
483 We want to show that $\alpha \in \Oh(\log n)$ | |
484 \end{center} | |
485 \end{frame} | |
486 | |
487 \begin{frame} | |
139
247f86a0ff6b
Typos in Frametitles
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
138
diff
changeset
|
488 \frametitle{Dual Program} |
129 | 489 |
490 \begin{block}{Dual Program} | |
141 | 491 Let $\Ih$ be the exponentially large set of \structure{all pathtrees}. |
129 | 492 \begin{alignat}{3} |
493 \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ % | |
494 \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\ | |
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 \\ | |
496 && \structure{\Ell} &\geq 0 | |
497 \end{alignat} | |
498 \end{block} | |
499 | |
500 \vfill | |
501 | |
502 \begin{center} | |
503 If $z \in \Oh(\log n)$ then $\alpha \in \Oh(\log n)$ by strong duality | |
504 \end{center} | |
125 | 505 \end{frame} |
506 | |
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 | 509 |
510 \begin{block}{Dual Program} | |
141 | 511 Let $\Ih$ be the exponentially large set of \structure{all pathtrees}. |
125 | 512 \begin{alignat}{3} |
129 | 513 \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ % |
125 | 514 \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\ |
129 | 515 \only<-2>{ |
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 \\ | |
517 } | |
518 \only<3-4>{ | |
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 \\ | |
520 } | |
521 \only<5->{ | |
522 && \structure{z} & \leq \min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)\\ | |
523 } | |
125 | 524 && \structure{\Ell} &\geq 0 |
525 \end{alignat} | |
526 \end{block} | |
129 | 527 |
528 \vfill | |
529 | |
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 | 532 \item They define a \structure{shortest path metric $d_{\structure{\ell}}(u, v)$} |
533 \item For an edge $e = (x, y)$ we write $d_{\structure{\ell}}(e) \defeq d_{\structure{\ell}}(x, y)$ | |
534 \end{itemize} | |
535 \begin{tikzpicture}[remember picture, overlay] | |
536 \only<2> {% | |
537 \node[fit=(a)(b), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below:{$\geq d_{\structure{\ell}}(e_T)$}}] {}; | |
538 } | |
539 \only<4> {% | |
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$}}] {}; | |
541 } | |
542 \end{tikzpicture} | |
125 | 543 \end{frame} |
544 | |
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 | 547 |
129 | 548 \begin{block}{Dual Program} |
141 | 549 Let $\Ih$ be the exponentially large set of \structure{all pathtrees}. |
129 | 550 \only<1-2>{% |
551 \begin{alignat}{3} | |
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)}\\ | |
553 \st \quad && \tikzmark{a}\sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1\tikzmark{b} \\ | |
554 && \structure{\Ell} &\geq 0 | |
555 \end{alignat} | |
556 \vspace{-1em} | |
557 } | |
558 \only<3>{% | |
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 | 561 \st \quad & \structure{\Ell} \geq 0 |
562 \end{alignat} | |
563 } | |
564 \end{block} | |
565 | |
566 \vfill | |
567 | |
568 \uncover<2-3>{ | |
569 \begin{itemize} | |
570 \item Now suppose | |
571 \begin{align} | |
572 \sum_{u, v \in V} c_{uv} \ell_{uv} = \beta > 0 | |
573 \end{align} | |
574 \item If we scale every length by $\frac{1}{\beta}$ our solution will change by $\frac{1}{\beta}$ | |
575 \end{itemize} | |
576 } | |
577 \begin{tikzpicture}[remember picture, overlay] | |
578 \only<2>{ | |
579 \node[fit=(a)(b), highlight, minimum height=2.5em, inner sep=-3pt] {}; | |
580 } | |
581 \end{tikzpicture} | |
125 | 582 \end{frame} |
583 | |
584 \begin{frame} | |
138 | 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 | 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 | 697 (m) node[below=0.05] {a} |
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 | 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 | 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 | 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 | 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 | 800 \end{frame} |
801 | |
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 | 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 | 841 \end{frame} |
842 | |
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 | 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 | 865 \end{frame} |
866 | |
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 | 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 | 908 \end{frame} |
909 | |
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 | 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 | 950 \end{frame} |
951 | |
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 | 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 | 1012 \end{frame} |
1013 | |
124 | 1014 \end{document} |