# HG changeset patch # User Markus Kaiser # Date 1400414878 -7200 # Node ID b948ace51db75bfeee86f8ab7793f8d344fc6308 # Parent 2af28ac8a070c5b30d44c3393f0884d2bc6a5e55 more frames on the way to the linear program diff -r 2af28ac8a070 -r b948ace51db7 minimum_bisection/presentation.tex --- a/minimum_bisection/presentation.tex Sun May 18 00:49:24 2014 +0200 +++ b/minimum_bisection/presentation.tex Sun May 18 14:07:58 2014 +0200 @@ -109,45 +109,219 @@ \end{frame} \begin{frame} - \frametitle{Oblivious Routing} + \frametitle{Routing with a Spanning Tree} + + \begin{itemize} + \item Choose any \structure{spanning tree $T$} of $G$ + \item Routing along its unique paths is a feasible solution + \item But probably not a good one + \end{itemize} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges - \begin{center} - \begin{tikzpicture}[flow graph] - \flownodes - \flowedges - \flowtreeedges + \only<2-> { + \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); + } + + \only<3-> { + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in {l/m,m/e,e/d,d/k,k/j,j/i} + \draw[tree edge, tumred] (\source.center) edge (\dest.center); + \end{pgfonlayer} + } + + \only<4-> { \flowcapacities - \flowdemands - - \begin{pgfonlayer}{background} - \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(g)(i)(k)(j), inner sep=3pt] {}; - \end{pgfonlayer} - \end{tikzpicture} - \end{center} + \node[below=0.2 of b] {\structure{$\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{10}{2} = 5$}}; + } + \end{tikzpicture} \end{frame} \begin{frame} - \frametitle{Definitions} + \frametitle{Tree Splits} \begin{itemize} - \item Graph - \item Spanning Tree - \item Cut - \item Demand - \item Congestion + \item Removing one edge $e_T$ from a ST creates a \structure{node partition $S(e_T)$} + \item Every such partition has a \structure{capacity $C(e_T)$} + \item And a \structure{demand $D(e_T)$} + \end{itemize} + \begin{align}{} + C(e_T) &= \sum_{\substack{u \in S(e_T), \\ v \not\in S(e_T)}} c_{uv} & + D(e_T) &= \sum_{\substack{u \in S(e_T), \\ v \not\in S(e_T)}} c_{uv} + \end{align} + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges + + \only<2-> { + \begin{pgfonlayer}{marked} + \draw[tree edge, tumred] (m.center) edge (e.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=3pt] (el) {}; + \end{pgfonlayer} + + \path (el) + ++ (200:1.5) + ++ (0, -0.5) coordinate (label); + \node[below=0 of label] {\structure{$S(\alert{e_T})$}}; + } + + \only<3> { + \flowcapacities + + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in {l/h,m/e,m/f,n/b} + \draw[tree edge, tumorange] (\source.center) edge (\dest.center); + \end{pgfonlayer} + } + + \only<3-> { + \node[below=0.5 of label] {$C(e_T) = 10$}; + } + + \only<4-> { + \flowdemands + + \begin{pgfonlayer}{demand} + \foreach \source/\dest/\demand/\pos/\bendage in { + {n/j/10/0.2/right}, + {n/h/12/0.7/left}, + {k/m/5/0.8/right}} + \draw[demand edge, bend \bendage=15, tumorange] (\source) edge node[flow demand, text=tumorange, pos=\pos]{\demand} (\dest); + \end{pgfonlayer} + + \node[below=1 of label] {$D(e_T) = 27$}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Optimal solution} + + \begin{lemma} + For any tree $T$ and any tree edge $e_T$, we know that for \alert{any routing} in $G$ there must be an edge with \structure{congestion} + \begin{align} + \rho_e \geq \frac{D(e_T)}{C(e_T)} + \end{align} + And therefore the \structure{optimal solution $\rho^\ast$} can be no better. + \end{lemma} + + \vfill + \pause + + \begin{itemize} + \item Suppose we find a tree such that for some $\alpha$ + \begin{align} + \forall e_T \in E_T.\quad c_{e_T} \geq \frac{1}{\alpha} C(e_T) + \end{align} + \item Then we have + \begin{align} + \structure{\rho_T} = \max_{e_T} \frac{D(e_T)}{c_{e_T}} \structure{\leq} \alpha \max_{e_T} \frac{D(e_T)}{C(e_T)} \leq \structure{\alpha \rho^\ast} + \end{align} \end{itemize} \end{frame} \begin{frame} - \frametitle{Routing with a Tree} + \frametitle{Routing with multiple spanning trees} + + \begin{itemize} + \item Choose a \structure{set of spanning trees $\left\{ T_i \right\}$} of $G$ + \item And a \structure{convex combination $\lambda$} with $\sum_i \lambda_i = 1$, $\lambda \geq 0$ + \item Routing is now split according to this combination. For $e \in E$ + \begin{align} + f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e) + \end{align} + \end{itemize} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + + \draw + (l) node[above right] {\structure{u}} + (i) node[above right] {\structure{v}}; + \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i); + + \path + (n) + ++ (-1, -0.5) coordinate (label); - content + \only<2> { + \flowtreeedges + } + + \only<2-> { + \node[tumgreen, below=0 of label, anchor=west] {$\lambda_1 = \frac{1}{2}$}; + } + + \only<3> { + \flowtreeedgestwo[tumorange] + } + + \only<3-> { + \node[tumorange, below=0.5 of label, anchor=west] {$\lambda_2 = \frac{1}{2}$}; + } + + \only<4-> { + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in {l/m,m/e,e/d,d/k,k/j,j/i} + \draw[tree edge, tumgreen] (\source.center) edge (\dest.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in {l/h,h/i} + \draw[tree edge, tumorange] (\source.center) edge (\dest.center); + \end{pgfonlayer} + } + + \only<5-> { + \flowcapacities + \node[below=1 of label, anchor=west] {\structure{$\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{5}{2} = 2.5$}}; + } + \end{tikzpicture} \end{frame} \begin{frame} - \frametitle{Routing with convex Combinations} + \frametitle{Routing with multiple spanning trees} - content + \begin{itemize} + % \item Remember that the total flow on edge $e \in E$ is + % \begin{align} + % f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e) + % \end{align} + \item Suppose we now find a \structure{set of trees} such that for some $\alpha$ + \begin{align} + \forall e \in E.\quad c_{e} \geq \frac{1}{\alpha} \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e) + \end{align} + \vfill + \item Then we have + \begingroup + \addtolength{\jot}{.5em} + \begin{align} + \structure{\rho} &= \hphantom{\alpha}\max_{e} \frac{f(e)}{c_{e}} \\ + &= \hphantom{\alpha}\max_{e} \frac{\sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)}{c_e} \\ + &\structure{\leq} \alpha \max_{e} \frac{\sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)}{\sum_{\substack{i:\\e \in T_i}} \lambda_i C_i(e)} \\ + &\leq \alpha \max_{e} \max_{i} \frac{D_i(e)}{C_i(e)} \leq \structure{\alpha \rho^\ast} + \end{align} + \endgroup + \end{itemize} \end{frame} \begin{frame} diff -r 2af28ac8a070 -r b948ace51db7 minimum_bisection/tikzpictures.tex --- a/minimum_bisection/tikzpictures.tex Sun May 18 00:49:24 2014 +0200 +++ b/minimum_bisection/tikzpictures.tex Sun May 18 14:07:58 2014 +0200 @@ -81,8 +81,17 @@ % {a/b}, {c/b}, {c/d}, {e/d}, {e/f}, {g/i}, - {h/e}, {h/i}, {i/j}, {k/j}, - {l/h}, {l/m}, {n/m}} + {m/e}, {d/k}, {i/j}, {k/j}, + {h/i}, {l/m}, {n/m}} \draw[tree edge, #1] (\source.center) edge (\dest.center); \end{pgfonlayer} } +\newcommand{\flowtreeedgestwo}[1][]{% + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in { + {n/l}, {l/h}, {h/i}, {i/g}, {i/j}, + {j/k}, {g/d}, {d/c}, {g/e}, {c/f}, + {f/m}, {f/b}} + \draw[tree edge, #1] (\source.center) edge (\dest.center); + \end{pgfonlayer} +}