# HG changeset patch # User Markus Kaiser # Date 1404593450 -7200 # Node ID 8c10f9532afcbf2f68c201bfbabc881903dae86d # Parent 4d5bf308e7ad8e2218642a6b544b55d8dd75255d add most of the math diff -r 4d5bf308e7ad -r 8c10f9532afc minimum_bisection/paper/preamble.tex --- a/minimum_bisection/paper/preamble.tex Sat Jul 05 20:25:20 2014 +0200 +++ b/minimum_bisection/paper/preamble.tex Sat Jul 05 22:50:50 2014 +0200 @@ -6,9 +6,9 @@ \usepackage[utf8]{inputenc} \usepackage{amsmath} +\usepackage{amssymb} \usepackage{mathdots} \usepackage{mathtools} -\mathtoolsset{showonlyrefs,showmanualtags} \usepackage{mathrsfs} \usepackage{csquotes} @@ -23,6 +23,9 @@ \usepackage[pdftex]{hyperref} \usepackage[nameinlink, capitalize]{cleveref} +% \newcommand{\blindtext}{Blindtext!} +\usepackage[math]{blindtext} + \newcommand{\R}{\mathbb{R}} \newcommand{\Oh}{\mathcal{O}} \newcommand{\Ih}{\mathcal{I}} @@ -49,3 +52,8 @@ % Dummy commands to reuse beamer code \newcommand{\structure}[1]{#1} \newcommand{\alert}[1]{#1} + +% LLNCS algorithms +\makeatletter +\spn@wtheorem{algorithm}{Algorithm}{\bfseries}{\itshape} +\makeatother diff -r 4d5bf308e7ad -r 8c10f9532afc minimum_bisection/paper/term_paper.tex --- a/minimum_bisection/paper/term_paper.tex Sat Jul 05 20:25:20 2014 +0200 +++ b/minimum_bisection/paper/term_paper.tex Sat Jul 05 22:50:50 2014 +0200 @@ -11,13 +11,39 @@ \maketitle \thispagestyle{plain} \begin{abstract} - I am an 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] @@ -60,6 +86,67 @@ \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 @@ -144,12 +231,78 @@ Dual \begin{alignat}{3} - \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ % + \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 \\ + && \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] @@ -186,8 +339,30 @@ \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] @@ -212,6 +387,65 @@ \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