Mercurial > latex

changeset 127:c213b1f538ed

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
captain! we have reached the primal program!
author Markus Kaiser <markus.kaiser@in.tum.de>
date Sun, 18 May 2014 14:51:50 +0200
parents b948ace51db7
children f753b74f0e72
files minimum_bisection/presentation.tex minimum_bisection/tikzpictures.tex
diffstat 2 files changed, 139 insertions(+), 8 deletions(-) [+]
line wrap: on
line diff
--- 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}
--- 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);