# HG changeset patch # User Markus Kaiser # Date 1406652581 -7200 # Node ID c02cfd41bcc49e948b25765a890d37ea3fefd804 # Parent 492a4baaeb86ee1acbbfac35ec9b5aa271fb4864 remove one approximation diff -r 492a4baaeb86 -r c02cfd41bcc4 minimum_bisection/paper/term_paper.tex --- a/minimum_bisection/paper/term_paper.tex Tue Jul 29 18:17:10 2014 +0200 +++ b/minimum_bisection/paper/term_paper.tex Tue Jul 29 18:49:41 2014 +0200 @@ -188,15 +188,6 @@ f_e &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e) \end{align} where we denote the demand of the split introduced by $T_i$ using some edge $e \in T_i$ as $D_i(e)$. -Suppose we find a set of trees such that -\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), - \intertext{we can again bound its congestion by the optimal solution using \cref{lem:optimal}.} - \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} This solution scheme is still too strict though and we want to allow more sophisticated structures. Instead of using the spanning trees directly, we interpret every node on a $u$-$v$-path of $T_i$ as an intermediate point on a path from $u$ to $v$. @@ -258,7 +249,7 @@ If we again suppose to find a set of path trees such that \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}) - \intertext{we get the now familiar bound, again using \cref{lem:optimal}.} + \intertext{we can again bound its congestion by the optimal solution using \cref{lem:optimal}.} \rho &= \hphantom{\alpha}\max_{\structure{e}} \frac{f_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 @@ -317,51 +308,6 @@ \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] @@ -392,10 +338,52 @@ \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} + \caption{ +To proof the desired approximation guarantee we now approximate $d_\ell$ using a result obtained about tree metrics from \cite{approx}. +To proof the desired approximation guarantee we now approximate $d_\ell$ using a result obtained about tree metrics from \cite{approx}. +To proof the desired approximation guarantee we now approximate $d_\ell$ using a result obtained about tree metrics from \cite{approx}.} \label{fig:sum_over_capacities} \end{figure} +To proof the desired approximation guarantee we now approximate $d_\ell$ using a result obtained about tree metrics 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} + +To be able to apply this result to our dual, we first need to show one more lemma. +We need to rewrite the enumerator in \cref{eq:dual_compact} to not sum over tree edges but all edges in the graph. +\begin{lemma} + Let $T$ be a spanning tree and $(V, M)$ a tree metric of $G = (V, E)$. + Then it holds that + \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} + See \cref{fig:sum_over_capacities}. +\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} + \section{Minimum Bisection} \label{sec:minimum_bisection} \blindtext