\input{preamble.tex}
\input{tikzpictures.tex}

\title{Oblivious Routing and Minimum Bisection}
\subtitle{Seminar: Approximation Algorithms}
\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
\date{June 3, 2014}

\begin{document}
\begin{frame}
    \titlepage
\end{frame}

\begin{frame}
    \frametitle{Flow Problems}
    \begin{problem}[Single Commodity Flow]
        Given
        \begin{itemize}[<+->]
            \item An (un)directed Graph $G = (V, E)$
            \item A \structure{capacity function} $c : E \to \R^+$
            \item A source $s$ and a target $t$
        \end{itemize}
        \uncover<4->{Calculate a maximum possible \structure{flow} $f : E \to \R^+$ through $G$.}
    \end{problem}

    \centering
    \begin{tikzpicture}[flow graph]
        \flownodes
        \flowedges[directed]
        \only<2->{\flowcapacities}

        \draw<3->
            (n.south) node[below] {\structure{s}}
            (j.south) node[below] {\structure{t}};
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Flow Problems}

    \begin{problem}[Multi Commodity Flow]
        Given
        \begin{itemize}
            \item An undirected Graph $G = (V, E)$
            \item A capacity function $c : E \to \R^+$
            \item<2-> A \structure{demand function} $d : V^2 \to \R^+$
        \end{itemize}
        \uncover<3->{Calculate a flow $f$ with least \structure{congestion $\rho = \max_{e \in E}\frac{f_e}{c_e}$}.}
    \end{problem}

    \centering
    \begin{tikzpicture}[flow graph]
        \flownodes
        \flowedges
        \flowcapacities
        \only<2->{\flowdemands}
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Oblivious Routing}

    \begin{problem}[Oblivious Routing]
        Given
        \begin{itemize}
            \item An undirected Graph $G = (V, E)$
            \item A capacity function $c : E \to \R^+$
        \end{itemize}
        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.
    \end{problem}

    \centering
    \begin{tikzpicture}[flow graph]
        \flownodes
        \flowedges
        \flowcapacities

        \draw<2->
            (n.south) node[below] {\structure{u}}
            (j.south) node[below] {\structure{v}};

        \only<3-> {
            \begin{pgfonlayer}{marked}
                \draw[marked edge, tumgreen]
                    (n.center) edge (l.center)
                    (l.center) edge (h.center)
                    (h.center) edge (i.center)
                    (i.center) edge (j.center);

                \draw[marked edge, tumblue]
                    (n.center) edge (m.center)
                    (m.center) edge (e.center)
                    (e.center) edge (c.center)
                    (c.center) edge (k.center)
                    (k.center) edge (j.center);

                \draw[marked edge, tumred]
                    (n.center) edge (b.center)
                    (b.center) edge (j.center);
            \end{pgfonlayer}

            \path[font=\Large]
                (n)
                +(-0.5, 0.5) node[tumgreen] {$\frac{1}{4}$}
                +(-0.5, 0) node[tumblue] {$\frac{1}{2}$}
                +(-0.5, -0.5) node[tumred] {$\frac{1}{4}$};
        }
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \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
    \end{itemize}

    \vfill

    \centering
    \begin{tikzpicture}[flow graph]
        \flownodes
        \flowedges
        \flowtreeedges

        \only<2-> {
            \draw
                (l) node[above right] {\structure{u}}
                (i) node[above right] {\structure{v}};
                \begin{pgfonlayer}{demand}
                    \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i);
                \end{pgfonlayer}
        }

        \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
            \node[below=0 of b] {\structure{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{10}{2} = 5$}};
        }
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Tree Splits}

    \begin{itemize}
        \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 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}};

        \path
            (n)
            ++ (-1, -0.5) coordinate (label);

        \only<2> {
            \flowtreeedges
        }

        \only<2-> {
            \node[tumgreen, below=0 of label, anchor=west] {$\displaystyle\lambda_1 = \frac{1}{2}$};
        }

        \only<3> {
            \flowtreeedgestwo[tumorange]
        }

        \only<3-> {
            \node[tumorange, below=0.5 of label, anchor=west] {$\displaystyle\lambda_2 = \frac{1}{2}$};
        }

        \only<4-> {
            \begin{pgfonlayer}{demand}
                \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{10} (i);
            \end{pgfonlayer}

            \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{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{5}{2} = 2.5$}};
        }
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Routing with multiple Spanning Trees}

    \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 C_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}
    \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_T : E_T \to E^+$
    \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
        }

        \only<2-> {
            \node[tumgreen, below=0 of label, anchor=west] {$\displaystyle\lambda_1 = \frac{2}{3}$};
        }

        \only<3> {
            \flowtreeedgestwo[tumorange]
        }

        \only<3-> {
            \node[tumorange, below=0.5 of label, anchor=west] {$\displaystyle\lambda_2 = \frac{1}{3}$};
        }

        \only<4-> {
            \begin{pgfonlayer}{demand}
                \draw[demand edge, bend left=10] (l) edge node[flow demand, pos=0.2]{9} (i);
            \end{pgfonlayer}

            \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{$\displaystyle\rho = \max_{e \in E} \frac{f_e}{c_e} = \frac{6}{4} = 1.5$}};
        }
    \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}
                    \rho &= \hphantom{\alpha}\max_{\structure{e}} \frac{f(\structure{e})}{c_{\structure{e}}} \\
                        &\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 \alpha \rho^\ast
                \end{align}
            \endgroup
    \end{itemize}

    \vfill

    \only<2> {
        \begin{center}
            How do we find such a set of trees? How large is $\alpha$?
        \end{center}
    }
\end{frame}

\begin{frame}
    \frametitle{Primal program}

    \begin{block}{Primal Program}
        Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.\\
        We want to find the best trees with smallest $\alpha$.
        \begin{alignat}{3}
            \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\
            \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 \\
            && \sum_{i \in \Ih} \structure{\lambda_i} &= 1 \\
            && \structure{\lambda} &\geq 0
        \end{alignat}
    \end{block}

    \vfill

    \begin{center}
        We want to show that $\alpha \in \Oh(\log n)$
    \end{center}
\end{frame}

\begin{frame}
    \frametitle{Dual Program}

    \begin{block}{Dual Program}
        Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.
        \begin{alignat}{3}
            \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ %
            \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\
            && \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 \\
            && \structure{\Ell} &\geq 0
        \end{alignat}
    \end{block}

    \vfill

    \begin{center}
        If $z \in \Oh(\log n)$ then $\alpha \in \Oh(\log n)$ by strong duality
    \end{center}
\end{frame}

\begin{frame}
    \frametitle{Solution of the Dual Program}

    \begin{block}{Dual Program}
        Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.
        \begin{alignat}{3}
            \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ %
            \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\
            \only<-2>{
                && \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 \\
            }
            \only<3-4>{
                && \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 \\
            }
            \only<5->{
                && \structure{z} & \leq \min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)\\
            }
            && \structure{\Ell} &\geq 0
        \end{alignat}
    \end{block}

    \vfill

    \begin{itemize}
        \item We interpret the $\structure{\ell_{uv}}$ as edge lengths in $G$
        \item They define a \structure{shortest path metric $d_{\structure{\ell}}(u, v)$}
        \item For an edge $e = (x, y)$ we write $d_{\structure{\ell}}(e) \defeq d_{\structure{\ell}}(x, y)$
    \end{itemize}
    \begin{tikzpicture}[remember picture, overlay]
        \only<2> {%
            \node[fit=(a)(b), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below:{$\geq d_{\structure{\ell}}(e_T)$}}] {};
        }
        \only<4> {%
            \node[fit=(c)(d), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below right:{$\geq \min_{i \in \Ih} \cdots$}}] {};
        }
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Solution of the Dual Program}

    \begin{block}{Dual Program}
        Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.
        \only<1-2>{%
            \begin{alignat}{3}
                \max_{\structure{\Ell}} \quad & \mathrlap{\min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)}\\
                \st \quad && \tikzmark{a}\sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1\tikzmark{b} \\
                && \structure{\Ell} &\geq 0
            \end{alignat}
            \vspace{-1em}
        }
        \only<3>{%
            \begin{alignat}{3}
                \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}}}\\
                \st \quad & \structure{\Ell} \geq 0
            \end{alignat}
        }
    \end{block}

    \vfill

    \uncover<2-3>{
        \begin{itemize}
            \item Now suppose
                \begin{align}
                    \sum_{u, v \in V} c_{uv} \ell_{uv} = \beta > 0
                \end{align}
            \item If we scale every length by $\frac{1}{\beta}$ our solution will change by $\frac{1}{\beta}$
        \end{itemize}
    }
    \begin{tikzpicture}[remember picture, overlay]
        \only<2>{
            \node[fit=(a)(b), highlight, minimum height=2.5em, inner sep=-3pt] {};
        }
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Tree Metric}

    \begin{theorem}[Tree Metric]
        For our metric $d_\ell$ there exists a \structure{tree metric $(V, M)$} with
        \begingroup
            \addtolength{\jot}{.5em}
            \begin{alignat}{2}
                d_\ell(u, v) &\leq M_{uv} & \forall u, v \in V\\
                \sum_{u, v \in V} c_{uv} M_{uv} &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v)
            \end{alignat}
        \endgroup
    \end{theorem}

    \vfill

    \centering
    \begin{tikzpicture}[grow=down, level distance = 25]
        \begin{scope}
            \tikzstyle{every node} = [draw, flow node]
            \tikzstyle{edge from parent} = [draw, edge]

            \tikzstyle{level 1} = [sibling distance = 100]
            \tikzstyle{level 2} = [sibling distance = 50]
            \tikzstyle{level 3} = [sibling distance = 30]
            \node[label=above:$z$] (z) {}
                child {
                    node[label=above left:$y$] (y) {}
                    edge from parent
                    child {
                        node[label=above left:$x$] (x) {}
                        edge from parent
                        child {
                            node[label=below left:$\structure{u}$] (u) {}
                            edge from parent
                        }
                        child {
                            node {}
                            edge from parent
                        }
                    }
                    child {
                        node {}
                        edge from parent
                        child {
                            node {}
                            edge from parent
                        }
                        child {
                            node {}
                            edge from parent
                        }
                    }
                }
                child {
                    node[label=above right:$\structure{v}$] (v) {}
                    edge from parent
                    child {
                        node {}
                        edge from parent
                        child {
                            node {}
                            edge from parent
                        }
                        child {
                            node {}
                            edge from parent
                        }
                    }
                    child {
                        node {}
                        edge from parent
                        child {
                            node {}
                            edge from parent
                        }
                        child {
                            node {}
                            edge from parent
                        }
                    }
                };
        \end{scope}

        \begin{pgfonlayer}{marked}
            \foreach \source/\dest in {u/x,x/y,y/z,z/v}
            \draw [tree edge, tumred] (\source.center) -- (\dest.center);
        \end{pgfonlayer}

        \node at (0, -3.5) {$M_{uv} = M_{ux} + M_{xy} + M_{yz} + M_{zv}$};
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Sum over all capacities}

    \begin{lemma}[]
        Let $T$ be a spanning tree and $(V, M)$ a tree metric of $G = (V, E)$. Then
        \begin{align}
            \sum_{(x, y) \in E_T} C(x, y) M_{xy} = \sum_{(u, v) \in E} c_{uv} M_{uv}
        \end{align}
    \end{lemma}

    \vfill

    \centering
    \begin{tikzpicture}[flow graph]
        \flownodes
        \flowedges
        \flowtreeedges

        \draw
            (n) node[above=0.1] {\structure{u}}
            (m) node[below=0.05] {a}
            (e) node[below=0.05] {b}
            (d) node[above=0.1] {c}
            (c) node[below=0.05] {d}
            (b) node[above=0.1] {\structure{v}};

        \path
            (n) -- node[node on edge] {$c_{uv}$} (b);

        \begin{pgfonlayer}{marked}
            \draw[tree edge, tumorange] (n.center) edge (b.center);
        \end{pgfonlayer}

        \only<2> {
            \begin{pgfonlayer}{marked}
                \draw[tree edge, tumred] (n.center) edge (m.center);
            \end{pgfonlayer}

            \begin{pgfonlayer}{background}
                \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(n), inner sep=15pt] (el) {};
            \end{pgfonlayer}
        }
        \only<3> {
            \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}
        }
        \only<4> {
            \begin{pgfonlayer}{marked}
                \draw[tree edge, tumred] (e.center) edge (d.center);
            \end{pgfonlayer}

            \begin{pgfonlayer}{background}
                \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m)(e)(f), inner sep=3pt] (el) {};
            \end{pgfonlayer}
        }
        \only<5> {
            \begin{pgfonlayer}{marked}
                \draw[tree edge, tumred] (d.center) edge (c.center);
            \end{pgfonlayer}

            \begin{pgfonlayer}{background}
                \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=-10, fit=(c)(b), inner sep=3pt] (el) {};
            \end{pgfonlayer}
        }
        \only<6> {
            \begin{pgfonlayer}{marked}
                \draw[tree edge, tumred] (c.center) edge (b.center);
            \end{pgfonlayer}

            \begin{pgfonlayer}{background}
                \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(b), inner sep=15pt] (el) {};
            \end{pgfonlayer}
        }
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Value of the Dual Problem}

    \begin{block}{Dual Program}
        Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.
        \begin{alignat}{3}
            \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}}}\\
            \st \quad & \structure{\Ell} \geq 0
        \end{alignat}
    \end{block}

    For any $\Ell$ we know that for the \structure{minimizing tree $T_i$} holds
    \begin{align}
        \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} \\
        &= \sum_{u, v \in V} c_{uv} M_{uv} \\
        &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v) \\
        &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} \ell_{uv} \\
        \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)
    \end{align}
\end{frame}

\begin{frame}
    \frametitle{Value of the Primal Program}

    \begin{block}{Primal Program}
        Let $\Ih$ be the exponentially large set of \structure{all pathtrees}.\\
        We want to find the best trees with smallest $\alpha$.
        \begin{alignat}{3}
            \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\
            \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 \\
            && \sum_{i \in \Ih} \structure{\lambda_i} &= 1 \\
            && \structure{\lambda} &\geq 0
        \end{alignat}
    \end{block}

    \vfill

    \begin{itemize}
        \item There is a $\structure{\lambda}$ such that $\structure{\alpha \in \Oh(\log n)}$
        \item But why are polynomially many trees enough?
        \item This gives an \alert{$\Oh(\log n)$-approximation}
    \end{itemize}
\end{frame}

\begin{frame}
    \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

        \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{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
    \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{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

        \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{Tree Bisections}

    \begin{lemma}[]
        For any spanning 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

        \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$}};

        \draw
            (b) node[below=0.05] {\structure{u}}
            (j) node[below=0.05] {\structure{v}};

        \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 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

    \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$}, giving an \alert{$\Oh(\log n)$-approximation}
        \item How to find the $X_i$?
    \end{itemize}
\end{frame}

\end{document}