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

\title{Oblivious Routing and Minimum Bisection}
\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
\institute{Technische Universit\"at M\"unchen\\
\email{markus.kaiser@in.tum.de}}

\begin{document}

\maketitle
\thispagestyle{plain}
\begin{abstract}
  I am an abstract!
\end{abstract}

\section{Oblivious Routing}
\label{sec:oblivious_routing}
\subsection{Problem definition}
\label{sub:or_problem}
\begin{figure}[tb]
    \centering
    \begin{tikzpicture}[flow graph]
        \path[use as bounding box] (-4, 2.4) rectangle (3.5,6.15);
        \flownodes
        \flowedges

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

        \begin{pgfonlayer}{demand}
            \draw[demand edge, bend left=20] (n) edge (j);
        \end{pgfonlayer}

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

        \node at (-0.25, 2.4) {$\lambda_{green} = 0.25 \qquad \lambda_{blue} = 0.5 \qquad \lambda_{red} = 0.25$};
    \end{tikzpicture}
    \caption{Oblivious Routing}
    \label{fig:oblivous_routing}
\end{figure}

\subsection{Formulation as a linear program}
\label{sub:or_lp}

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

        \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) coordinate (label);
        \node[below of = label] {\structure{$S(\alert{e_T})$}};

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

        \begin{pgfonlayer}{marked}
            \draw[tree edge, tumblue] (m.center) edge (e.center);
        \end{pgfonlayer}
        \path (m) -- node[flow capacity]{$e_T$} (e);
    \end{tikzpicture}

    \caption{Tree splits}
    \label{fig:tree_splits}
\end{figure}

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

        \draw
            (l) node[above=3] {\structure{u}}
            (i) node[above=3] {\structure{v}}
            (e) node[above left] {\structure{x}}
            (d) node[above=3] {\structure{z}}
            (c) node[below=3] {\structure{y}} ;

        \begin{pgfonlayer}{demand}
            \draw[demand edge, bend left=10] (l) edge (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}
    \end{tikzpicture}
    \caption{Routing with Pathtrees}
    \label{fig:pathtrees}
\end{figure}

Primal
\begin{alignat}{3}
    \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}} \label{eq:primal}\\
    \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}

\subsection{Approximation guarantee using the dual}
\label{sub:or_approx}

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

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

        \draw
            (n) node[above=3] {\structure{u}}
            (m) node[below=3] {a}
            (e) node[below=3] {b}
            (d) node[above=3] {c}
            (c) node[below=3] {d}
            (b) node[below=3] {\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}

        \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=8pt] (el) {};
        \end{pgfonlayer}
    \end{tikzpicture}
    \caption{Sum over all Capacities}
    \label{fig:sum_over_capacities}
\end{figure}

\section{Minimum Bisection}
\label{sec:minimum_bisection}
\subsection{Problem definition}
\label{sub:mb_problem}
\begin{figure}[tb]
    \centering
    \begin{tikzpicture}[flow graph]
        \flownodes
        \flowedges

        \begin{pgfonlayer}{background}
            \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(c)(d)(g)(k)(j)(i)(e)(h), inner sep=3pt] (el) {};
        \end{pgfonlayer}

        \path (el)
            ++ (-30:2.6) node {\structure{$S$}};

        \begin{pgfonlayer}{marked}
            \foreach \source/\dest in {b/j,f/c,f/e,m/e,l/h}
            \draw [tree edge, tumorange] (\source.center) -- (\dest.center);
        \end{pgfonlayer}
    \end{tikzpicture}
    \caption{Minimum Bisection}
    \label{fig:minimum_bisection}
\end{figure}

\subsection{Approximation using oblivious routing}
\label{sub:mb_approx}
\begin{figure}[tb]
    \begin{tikzpicture}[flow graph]
        \flownodes
        \flowedges
        \flowtreeedges

        \begin{pgfonlayer}{background}
            \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(c)(d)(g)(k)(j)(i)(e)(h), inner sep=3pt] (el) {};
        \end{pgfonlayer}

        \path (el)
            ++ (-30:2.6) node {\structure{$S$}};

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

        \begin{pgfonlayer}{marked}
            \foreach \source/\dest in {f/c,b/j,l/h}
            \draw [tree edge, tumblue, dash pattern=on 7pt off 7pt] (\source.center) -- (\dest.center);

            \foreach \source/\dest in {b/c,e/f,e/m}
            \draw [tree edge, tumred] (\source.center) -- (\dest.center);
        \end{pgfonlayer}

        \foreach \source/\dest/\name in {b/c/$e_3$,e/f/$e_2$,e/m/$e_1$}
        \path (\source) -- node[node on edge] {\name} (\dest);
    \end{tikzpicture}
    \caption{Costs are lower as tree costs}
    \label{fig:tree_bisections}
\end{figure}


\nocite{*}
\bibliographystyle{alpha}
\bibliography{term_paper}

\end{document}