# HG changeset patch # User Markus Kaiser # Date 1400417510 -7200 # Node ID c213b1f538ed1dab0fd0414d01ed1172038447db # Parent b948ace51db75bfeee86f8ab7793f8d344fc6308 captain! we have reached the primal program! diff -r b948ace51db7 -r c213b1f538ed minimum_bisection/presentation.tex --- a/minimum_bisection/presentation.tex Sun May 18 14:07:58 2014 +0200 +++ b/minimum_bisection/presentation.tex Sun May 18 14:51:50 2014 +0200 @@ -257,7 +257,6 @@ \draw (l) node[above right] {\structure{u}} (i) node[above right] {\structure{v}}; - \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i); \path (n) @@ -280,6 +279,8 @@ } \only<4-> { + \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i); + \begin{pgfonlayer}{marked} \foreach \source/ \dest in {l/m,m/e,e/d,d/k,k/j,j/i} \draw[tree edge, tumgreen] (\source.center) edge (\dest.center); @@ -308,7 +309,7 @@ % \end{align} \item Suppose we now find a \structure{set of trees} such that for some $\alpha$ \begin{align} - \forall e \in E.\quad c_{e} \geq \frac{1}{\alpha} \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e) + \forall e \in E.\quad c_{e} \geq \frac{1}{\alpha} \sum_{\substack{i:\\e \in T_i}} \lambda_i C_i(e) \end{align} \vfill \item Then we have @@ -325,9 +326,139 @@ \end{frame} \begin{frame} - \frametitle{Routing with convex Combinations and Pathtrees} + \frametitle{Pathtrees} + + \begin{itemize} + \item Identify every edge in a tree with a \structure{path} in $G$ + \item These paths can \structure{overlap} + \item For tree $T$ we get a mapping $P$ + \begin{align} + P : E_T \to E^+ + \end{align} + \end{itemize} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges + \flowcapacities + + \draw + (e) node[above right] {\structure{a}} + (d) node[above=0.1] {\structure{b}}; + + \only<2-> { + \begin{pgfonlayer}{marked} + \draw[tree edge, line width=4pt, white] (e.center) edge (d.center); + \draw[tree edge, densely dashed, tumgreen!80] (e.center) edge (d.center); + + \foreach \source/\dest in {e/c,c/d} + \draw[tree edge, tumblue!80] (\source.center) edge (\dest.center); + \end{pgfonlayer} + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Routing with multiple pathtrees} + + \begin{itemize} + \item Choose a \structure{set of pathtrees $\left\{ T_i \right\}$} of $G$ with \structure{combination $\lambda$} + \item Now route along the paths identified with edges. For $e \in E$ + \begin{align} + f(\structure{e}) &= \sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(\alert{e_T})}} D_i(\alert{e_T}) + \end{align} + \end{itemize} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + + \draw + (l) node[above right] {\structure{u}} + (i) node[above right] {\structure{v}}; + + \path + (n) + ++ (-1, -0.5) coordinate (label); + + \only<2> { + \flowtreeedges + } - content + \only<2-> { + \node[tumgreen, below=0 of label, anchor=west] {$\lambda_1 = \frac{2}{3}$}; + } + + \only<3> { + \flowtreeedgestwo[tumorange] + } + + \only<3-> { + \node[tumorange, below=0.5 of label, anchor=west] {$\lambda_2 = \frac{1}{3}$}; + } + + \only<4-> { + \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{9} (i); + + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in {l/m,m/e,d/k,k/j,j/i} + \draw[tree edge, tumgreen] (\source.center) edge (\dest.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{marked} + \draw[tree edge, line width=4pt, white] (e.center) edge (d.center); + \draw[tree edge, densely dashed, tumgreen!80] (e.center) edge (d.center); + + \foreach \source/\dest in {e/c,c/d} + \draw[tree edge, tumblue!80] (\source.center) edge (\dest.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in {l/h,h/i} + \draw[tree edge, tumorange] (\source.center) edge (\dest.center); + \end{pgfonlayer} + } + + \only<5-> { + \flowcapacities + \node[below=1 of label, anchor=west] {\structure{$\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{6}{4} = 2$}}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Routing with multiple pathtrees} + + \begin{itemize} + \item Again suppose we now find a \structure{set of trees} such that for some $\alpha$ + \begin{align} + \forall \structure{e} \in E.\quad c_{e} \geq \frac{1}{\alpha} \sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(\alert{e_T})}} C_i(\alert{e_T}) + \end{align} + \item Then we have + \begingroup + \addtolength{\jot}{.5em} + \begin{align} + \structure{\rho} &= \hphantom{\alpha}\max_{\structure{e}} \frac{f(\structure{e})}{c_{\structure{e}}} \\ + &\structure{\leq} \alpha \max_{\structure{e}} \frac{\sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(e_T)}} D_i(\alert{e_T})}{\sum_{i} \lambda_i \sum_{\substack{\alert{e_T} \in T_i:\\\structure{e} \in P_i(e_T)}} C_i(\alert{e_T})} \\ + &\leq \alpha \max_{\structure{e}} \max_{i} \frac{D_i(\structure{e})}{C_i(\structure{e})} \leq \structure{\alpha \rho^\ast} + \end{align} + \endgroup + \end{itemize} + + \vfill + + \only<2> { + \begin{center} + \Large How do we find such a set of trees? How large is $\alpha$? + \end{center} + } \end{frame} \begin{frame} diff -r b948ace51db7 -r c213b1f538ed minimum_bisection/tikzpictures.tex --- a/minimum_bisection/tikzpictures.tex Sun May 18 14:07:58 2014 +0200 +++ b/minimum_bisection/tikzpictures.tex Sun May 18 14:51:50 2014 +0200 @@ -39,8 +39,8 @@ {(-2,6)/l}, {(-2.5,5)/m}, {(-4,5)/n}} - \draw \pos\jiggle node[flow node] (\name) {}; - % \draw \pos\jiggle node[flow node, label={\name}, font=\footnotesize] (\name) {}; + % \draw \pos\jiggle node[flow node] (\name) {}; + \draw \pos\jiggle node[flow node, label={\name}, font=\footnotesize] (\name) {}; } \newcommand{\flowedges}[1][]{% \foreach \source/\dest in { @@ -57,9 +57,9 @@ \foreach \source/\dest/\capacity in { % {a/b}, {a/n}, {a/j}, {n/b/2}, {b/j/10}, {c/b/3}, {f/b/4}, - {c/d/1}, {e/d/2}, {e/f/4}, {g/i/2}, + {c/d/4}, {e/d/2}, {e/f/4}, {g/i/2}, {h/e/1}, {h/i/2}, {i/j/6}, {k/j/4}, - {l/h/3}, {l/m/3}, {n/m/5}, + {l/h/3}, {l/m/4}, {n/m/5}, {c/k/4}, {k/i/3}, {g/d/1}, {m/e/4}, {n/l/6}, {m/f/1}, {f/c/2}, {d/k/4}, {e/g/1}, {c/e/5}} \path (\source) -- node[flow capacity, #1]{\capacity} (\dest);