\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}
    \blindtext
\end{abstract}

\section{Oblivious Routing}
\label{sec:oblivious_routing}

\blindtext
\blindtext

\subsection{Problem definition}
\label{sub:or_problem}

\begin{definition}[Flow]
    A function $f : E \to \R^+$ assigning a throughput to every edge.
\end{definition}

\blindtext

\begin{definition}[Congestion]
    \begin{align}
        \rho = \max{e \in E} \frac{f_e}{c_e}
    \end{align}
\end{definition}

\blindtext

\begin{problem}[Oblivious Routing]
    Given an undirected Graph $G = (V, E)$ and an edge capacity function $c : E \to \R^+$.
    Calculate a combination of paths for each $(u, v) \in V^2$ such that for any demand function the congestion will be as small as possible.
\end{problem}

\blindtext

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

\begin{definition}[Tree Split]
    \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}
\end{definition}

Routing with a spanning tree.
\begin{align}
    f(e) &= D(e)
\end{align}
Suppose we find
\begin{align}
    \forall e_T \in E_T.\quad c_{e_T} &\geq \frac{1}{\alpha} C(e_T)
    \intertext{Then we have}
    \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}

\begin{lemma}
    For any tree $T$ and any tree edge $e_T$, we know that for any routing in $G$ there must be an edge with congestion
    \begin{align}
        \rho_e \geq \frac{D(e_T)}{C(e_T)}
    \end{align}
    And therefore the optimal solution $\rho^\ast$ can be no better.
\end{lemma}
\begin{proof}
    \blindtext
\end{proof}

Routing with Spanning Trees.
\begin{align}
    f(e) &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e)
    \intertext{suppose we find}
    \forall e \in E.\quad c_{e} &\geq \frac{1}{\alpha} \sum_{\substack{i:\\e \in T_i}} \lambda_i C_i(e)
    \intertext{then}
    \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}

\begin{definition}[Path Tree]
    A path tree of an undirected graph $G = (V, E)$ is a pair $(T, P)$ of a spanning tree $T$ of $G$ and a function $P : E_T \to E$ identifiing every edge $e_T = (x, y)$ of $T$ with a path in $G$ from $x$ to $y$.
\end{definition}

Routing with Path trees.
\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}
\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}
\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}

\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=8pt] (el) {};
        \end{pgfonlayer}

        \path (el)
            ++ (200:1)
            ++ (0, -0.5) 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}} \label{eq:dual}\\ %
    \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 \label{eq:dual_constraints}\\
    && \structure{\Ell} &\geq 0
\end{alignat}

Rewrite \cref{eq:dual_constraints}
\begin{align}
    \structure{z} & \leq \sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T) \qquad \forall i \in \Ih\\
    \intertext{And again}
    \structure{z} & \leq \min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)
\end{align}

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

Suppose $\sum_{u, v \in V} c_{uv} \ell_{uv} = \beta > 0$, then the solution changes by the same factor.
Thus rewrite finally
\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}}} \label{eq:dual_compact}\\
    \st \quad & \structure{\Ell} \geq 0
\end{alignat}

Then we use from \cite{approx}.
\begin{theorem}[Tree Metric]
    For any nonnegative set of costs $c_{uv}$ and any metric $d_\ell$ there exists a tree metric $(V, M)$ such that
    \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}

\blindtext

\begin{lemma}
    Let $T$ be a spanning tree and $(V, M)$ a tree metric of $G = (V, E)$. Then we can rewrite the sum over all edges of $T$ in \cref{eq:dual_compact} as a sum over all edges in $G$.
    \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}
\begin{proof}
    \blindtext
\end{proof}

\begin{lemma}
    The linear program has a value of $\Oh(\log n)$.
\end{lemma}
\begin{proof}
    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{proof}

\begin{theorem}
    There is an $\Oh(\log n)$ approximation algorithm for the minimum bisection problem.
\end{theorem}
\begin{proof}
    Use the upper guarantee, then apply ellipsoid method.
\end{proof}

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

\subsection{Problem definition}
\label{sub:mb_problem}
\begin{problem}[Minimum Bisection]
    Given an undirected Graph $G = (V, E)$ and an edge-cost function $c : E \to \R^+$.
    Find a set $S \subset V$ containing half the vertices with \structure{minimal split cost}.
\end{problem}

\blindtext

\begin{definition}[Tree Bisection]
    Given a spanning tree $T$ of $G$ with an edge $e_T \in E_T$.
    We define a new cost function $c_T : E_T \to \R^+$ based on the tree splits induced by the edges of $T$.
    The cost of a bisection $S$ is the sum of tree split costs of all tree edges cut by $S$.
    \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}
    The tree bisection of $T$ is an optimal solution of the minimum bisection problem with respect to the cost function $c_T$.
\end{definition}

\blindtext

\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{algorithm}
    \label{alg:minimum_bisection}
    Given graph $G = (V, E)$ and cost function $c : E \to \R^+$.
    \begin{enumerate}
        \item Interpret costs $c(e)$ as capacities
        \item Solve oblivious routing on $G$, obtaining trees $T_i$
        \item Find minimum tree bisections $X_i$ for all trees $T_i$
        \item Choose the $X_i$ with lowest $c(\delta(X_i))$
    \end{enumerate}
\end{algorithm}

\begin{lemma}
    For any spanning tree $T$ and any cut $S \subseteq V$ the cost of the cut is bounded above by the tree bisection of $T$.
    \begin{align}
        c(\delta(S)) \leq c_T(\delta(S))
    \end{align}
\end{lemma}
\begin{proof}
    \blindtext
\end{proof}

\blindtext

\begin{lemma}
    Let $\left\{ (T_i, \lambda_i) \mid i \in \Ih \right\}$ be a $\Oh(\log n)$-approximation to the oblivious flow problem.
    Then for any cut $S \subseteq V$ the convex combination of tree bisections is bounded above by the cost of $S$ times a logarithmic factor.
    \begin{align}
        \sum_i \lambda_i c_{T_i}(\delta(S)) \leq \Oh(\log n) c(\delta(S))
    \end{align}
\end{lemma}
\begin{proof}
    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}
    We sum up the inequalities for all $(u, v) \in \delta(S)$.
    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}
    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{proof}

\begin{theorem}
    \cref{alg:minimum_bisection} is an $\Oh(\log n)$ approximation algorithm for the minimum bisection problem.
\end{theorem}
\begin{proof}
    \blindtext
    \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}
\end{proof}

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