# HG changeset patch # User Markus Kaiser # Date 1400705124 -7200 # Node ID c0eb673db33ea7d41770062262f6fe1542ed0920 # Parent 782316b52e1ade287e9dc46e8955a507b42a894a finish minimum bisection presentation diff -r 782316b52e1a -r c0eb673db33e minimum_bisection/presentation.tex --- a/minimum_bisection/presentation.tex Wed May 21 18:02:50 2014 +0200 +++ b/minimum_bisection/presentation.tex Wed May 21 22:45:24 2014 +0200 @@ -114,11 +114,12 @@ \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 + \item The flow is defined by the demands of the splits. For $e_T \in E_T$ + \begin{align} + f(e_T) &= D(e_T) + \end{align} \end{itemize} - \vfill - \centering \begin{tikzpicture}[flow graph] \flownodes @@ -156,7 +157,7 @@ \item Every such partition has a \structure{capacity $C(e_T)$} \item And a \structure{demand $D(e_T)$} \end{itemize} - \begin{align}{} + \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} @@ -795,39 +796,217 @@ \begin{itemize} \item There is a $\structure{\lambda}$ such that $\structure{\alpha \in \Oh(\log n)}$ - \item The algorithm as an \alert{$\Oh(\log n)$-approximation} + \item The algorithm is an \alert{$\Oh(\log n)$-approximation} \item But why are polynomially many trees enough? \end{itemize} \end{frame} \begin{frame} - \frametitle{Minimum Bisection Problem} + \frametitle{Minimum Bisection} + + \begin{problem}[Minimum Bisection] + Given + \begin{itemize} + \item An undirected Graph $G = (V, E)$ + \item A cost function $c : E \to \R^+$ + \end{itemize} + Find a set $S \subset V$ containing half the vertices with \structure{minimal split cost}. + \end{problem} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowcapacities - content + \only<2-> { + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {}; + \end{pgfonlayer} + + \path (el) + ++ (-30:2.3) node {\structure{$S$}}; + } + + \only<3-4> { + \begin{pgfonlayer}{marked} + \foreach \source/\dest in {b/j,b/c,c/f,e/c,e/d,e/g,h/i} + \draw [tree edge, tumorange] (\source.center) -- (\dest.center); + \end{pgfonlayer} + + \path (n) + ++ (-0.5, -1.5) node[tumorange, anchor=west] {\alt<3>{$\hphantom{c(}\delta(S)$}{$c(\delta(S)) = 25$}}; + } + \end{tikzpicture} \end{frame} \begin{frame} - \frametitle{Solution Algorithm} + \frametitle{Approximation Algorithm} - content + \begin{block}{Minimum Bisection Approximation} + Given graph $G = (V, E)$ and cost function $c : E \to \R^+$. + \begin{enumerate} + \item Interpret costs $c(e)$ as \structure{capacities} + \item Solve oblivious routing on $G$, obtaining \structure{trees $T_i$} + \item Find minimum \structure{tree bisections $X_i$} for all trees $T_i$ + \item Choose the $X_i$ with \structure{lowest $c(\delta(X_i))$} + \end{enumerate} + \end{block} + + \vfill + \pause + + We have to show + \begin{itemize} + \item What the $X_i$ actually are + \item An \alert{$\Oh(\log n)$-approximation} guarantee + \item That we can find the $X_i$ in polynomial time + \end{itemize} \end{frame} \begin{frame} - \frametitle{Inequality Fun \#2} + \frametitle{Tree bisections} + + \begin{itemize} + \item Given a spanning tree $T$ of $G$ with an edge $e_T \in E_T$ + \item Define a new \structure{cost function $c_T$} using tree splits + \end{itemize} + \begin{align} + 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) + \end{align} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges - content + \only<2-> { + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {}; + \end{pgfonlayer} + + \path (el) + ++ (-30:2.3) node {\structure{$S$}}; + } + + \only<3> { + \begin{pgfonlayer}{marked} + \foreach \source/\dest in {b/c,e/d,h/i} + \draw [tree edge, tumred] (\source.center) -- (\dest.center); + \end{pgfonlayer} + + \foreach \source/\dest/\name in {b/c/$e_3$,e/d/$e_2$,h/i/$e_1$} + \path (\source) -- node[node on edge] {\name} (\dest); + + \path (n) + ++ (-1, -1.5) node[tumred, anchor=west] {$\displaystyle c_T(\delta(S)) = \sum_{k=1}^3 C(e_k)$}; + } + \end{tikzpicture} \end{frame} \begin{frame} - \frametitle{Inequality Fun \#2} + \frametitle{Tree bisections} + + \begin{lemma}[] + For any tree $T$ and any $S \subseteq V$ we have + \begin{align} + c(\delta(S)) \leq c_T(\delta(S)) + \end{align} + \end{lemma} + + \vfill + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges - content + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=45, fit=(c)(d)(g)(k)(j)(i), inner sep=3pt] (el) {}; + \end{pgfonlayer} + + \path (el) + ++ (-30:2.3) node {\structure{$S$}}; + + \begin{pgfonlayer}{marked} + \foreach \source/\dest in {b/j,f/c,e/c,e/g} + \draw [tree edge, tumblue, dash pattern=on 7pt off 7pt] (\source.center) -- (\dest.center); + + \foreach \source/\dest in {b/c,e/d,h/i} + \draw [tree edge, tumred] (\source.center) -- (\dest.center); + \end{pgfonlayer} + + \foreach \source/\dest/\name in {b/c/$e_3$,e/d/$e_2$,h/i/$e_1$} + \path (\source) -- node[node on edge] {\name} (\dest); + \end{tikzpicture} \end{frame} \begin{frame} - \frametitle{Tree goodness} + \frametitle{Tree Bisections} + + \begin{lemma}[] + Let $\left\{ T_i \right\}$ be a solution to the \structure{oblivious flow} problem on $G$.\\ + Then for any $S \subseteq V$ we have + \begin{align} + \sum_i \lambda_i c_{T_i}(\delta(S)) \leq \Oh(\log n) c(\delta(S)) + \end{align} + \end{lemma} + + \vfill - content + \begin{itemize} + \only<1> { + \item Remember from the primal program that \structure{for all $u, v \in V$} + \begin{align} + \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}} + \end{align} + \item We sum up the inequalities for all $(u, v) \in \delta(S)$ + } + \only<2> { + \item We sum up the inequalities for all $(u, v) \in \delta(S)$ + \item This gives us + \begin{align} + \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)) + \end{align} + \item We are done with the observation that + \begin{align} + 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) + \end{align} + } + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Approximation Algorithm} + + \begin{block}{Minimum Bisection Approximation} + Given graph $G = (V, E)$ and cost function $c : E \to \R^+$. + \begin{enumerate} + \item Interpret costs $c(e)$ as \structure{capacities} + \item Solve oblivious routing on $G$, obtaining \structure{trees $T_i$} + \item Find minimum \structure{tree bisections $X_i$} for all trees $T_i$ + \item Choose the $X_i$ with \structure{lowest $c(\delta(X_i))$} + \end{enumerate} + \end{block} + + \vfill + + \begin{itemize} + \item Let now $X^*, X_i$ be the optimal solutions on $G$ and the $T_i$. Then + \begin{align} + \sum_i \lambda_i c(\delta(X_i)) &\leq \sum_i \lambda_i c_{T_i}(\delta(X_i)) \\ + &\leq \sum_i \lambda_i c_{T_i}(\delta(X^*)) \\ + &\leq \Oh(\log n) c(\delta(X^*)) + \end{align} + \item This also holds for the \structure{best $X_i$} + \item How to find the $X_i$? + \end{itemize} \end{frame} \end{document}