\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{Oblivious Routing}

    \begin{center}
        \begin{tikzpicture}[flow graph]
            \flownodes
            \flowedges
            \flowtreeedges
            \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}
\end{frame}

\begin{frame}
    \frametitle{Definitions}

    \begin{itemize}
        \item Graph
        \item Spanning Tree
        \item Cut
        \item Demand
        \item Congestion
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Routing with a Tree}

    content
\end{frame}

\begin{frame}
    \frametitle{Routing with convex Combinations}

    content
\end{frame}

\begin{frame}
    \frametitle{Routing with convex Combinations and Pathtrees}

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