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

\title{Oblivious Routing and Minimum Bisection}
\subtitle{Approximation Algorithms Seminar}
\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
\date{May 28, 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 the 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 the 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
        \item But probably not a good one
    \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}};
            \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
            \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{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] {$\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-> {
            \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);
            \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 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$
            \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
        }

        \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}
    \frametitle{Primal Program}

    \begin{block}{Primal Program}
        \begin{alignat}{3}
            \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\
            \st \quad && \sum_i \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}} & \quad \forall \alert{u,v} \in V \\
            && \sum_i \structure{\lambda_i} &= 1 \\
            && \structure{\lambda} &\geq 0
        \end{alignat}
    \end{block}
\end{frame}

\begin{frame}
    \frametitle{Dual Program}

    \begin{block}{Dual Program}
        \begin{alignat}{3}
            \max_{\structure{\Ell, z}} \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}} & \quad \forall i \in \Ih \\
            && \structure{\Ell} &\geq 0
        \end{alignat}
    \end{block}
\end{frame}

\begin{frame}
    \frametitle{Proof of $\Oh(\log n)$ness}

    \begin{itemize}
        \item Distance Metric
        \item Normalization
        \item inequalities
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Polynomial Algorithm}

    content
\end{frame}

\begin{frame}
    \frametitle{Minimum Bisection Problem}

    content
\end{frame}

\begin{frame}
    \frametitle{Solution Algorithm}

    content
\end{frame}

\begin{frame}
    \frametitle{Inequality Fun \#2}

    content
\end{frame}

\begin{frame}
    \frametitle{Tree goodness}

    content
\end{frame}

\begin{frame}
    \frametitle{Solution of MB on trees}

    content
\end{frame}

\end{document}