# HG changeset patch # User Markus Kaiser # Date 1406650630 -7200 # Node ID 492a4baaeb86ee1acbbfac35ec9b5aa271fb4864 # Parent 59e62bb8c8dd4403c897ab632f63add4cb4ff203 rewrite the dual diff -r 59e62bb8c8dd -r 492a4baaeb86 minimum_bisection/paper/term_paper.tex --- a/minimum_bisection/paper/term_paper.tex Tue Jul 29 13:56:00 2014 +0200 +++ b/minimum_bisection/paper/term_paper.tex Tue Jul 29 18:17:10 2014 +0200 @@ -167,7 +167,7 @@ \end{lemma} We will use this observation to proof our approximation guarantee. -Suppose we find a spanning tree such that every edge has capacity of the capacity of the corresponding tree split times some factor $\alpha \geq 1$. +Suppose we find a spanning tree such that every edge has capacity of the capacity of the corresponding tree split divided by some factor $\alpha \geq 1$. \begin{align} \forall e_T \in E_T.\quad c_{e_T} &\geq \frac{1}{\alpha} C(e_T) \intertext{Using \cref{lem:optimal} we can bound the congestion of this spanning tree in relation to the optimal solution.} @@ -178,35 +178,30 @@ Note that this factor $\alpha$ is a property of the tree and not any specific demand function, thus we know that this tree yields a solution of cost at most $\alpha$ times the optimal solution for any demand. This tree does not have to exist however and therefore this approach will not yield any approximation guarantee. +Since oblivious routing allows us to define multiple $u$-$v$-paths, a natural extension is to consider not only one spanning tree but a convex combination of multiple spanning trees. +We denote each of these trees as some $T_i = (V, E_{T_i})$ and identify $e \in E_{T_i}$ with $e \in T_i$ for compactness. +Solutions of this kind are a set of trees and factors $\left\{ (T_i, \lambda_i) \right\}$ with $\lambda_i \geq 0$ and $\sum_i \lambda_i = 1$. -Routing with Spanning Trees. +For a given demand function, the demand $d_{uv}$ is routed through the unique $u$-$v$-paths in the trees $T_i$ according to the convex fractions. +For every edge $e$ in the original graph we get \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}} \\ + 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} -\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} +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$. +Instead of using the direct connections given by the tree edges to traverse the intermediate points, we are allowed to take any path in $G$. +A pair of spanning tree and set of paths connecting two neighboured nodes in the tree is called a path tree. \begin{figure}[tb] \centering @@ -238,16 +233,40 @@ \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} + % \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} + \caption{A path tree is a pair of a spanning tree $T$ and a mapping $P$ from its edges to arbitrary paths in $G$. Instead of routing the demand $d_{uv}$ along the green tree edges, the edge $(x, z)$ is replaced by the blue edges $P((x, z)) = ((x, y), (y, z))$.} \label{fig:pathtrees} \end{figure} -Primal +\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$ identifying every edge $e_T = (x, y)$ of $T$ with a path in $G$ from $x$ to $y$. +\end{definition} + +Note that the same edge in $G$ may well be used by multiple different paths in the same path tree. +To now route any demand $d_{uv}$ using a path tree, we move along the unique $u$-$v$-path in the tree and stitch together the paths corresponding to the edges in the path. + +Since if routing with spanning tree $T_i$ the flow through every tree edge $e_T$ would be $D_i(T_i)$, the same amount of flow must now be added to every edge on the path $P_i(e_T)$. +If we now consider a convex combination of path trees, the flow through every edge $e \in E$ is +\begin{align} + f_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} + +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}.} + \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 +\end{align} + +We will now show that there always is a solution using path trees such that $\alpha \in \Oh(\log n)$ and sketch how to find such a set of trees. +We denote the finite but exponentially sized set of all path trees over $G$ as $\Ih$. +We can then formulate a linear program which enforces the assumption that every edge capacity is large enough and chooses a set of path trees such that $\alpha$ is minimal. \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 \\ @@ -255,10 +274,13 @@ && \structure{\lambda} &\geq 0 \end{alignat} +To gain an $\Oh(\log n)$ approximation algorithm from this linear program, we have to show that $\alpha$ is of at most logarithmic size and that it is possible to solve this linear program with exponentially sized sums in polynomial time, yielding a solution of polynomially many path trees. + \subsection{Approximation guarantee using the dual} \label{sub:or_approx} -Dual +To proof the bound for the value of the linear program, we will consider the dual program and show that it is logarithmically bounded. +The dual problem has exponentially many constraints, one for each path tree, and a decision variable $\ell_{uv}$ for every pair of vertices. \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 \\ @@ -266,22 +288,30 @@ && \structure{\Ell} &\geq 0 \end{alignat} -Rewrite \cref{eq:dual_constraints} +We will rewrite this dual program to be able to apply a result about the approximation of metrics with tree metrics. +To this end we will interpret the variables $l_{uv}$ as distances between vertices and obtain a shortest path metric $d_\ell(u, v)$ which we will approximate later. For an edge $e = (x, y)$ we denote $d_\ell(e) \defeq d_\ell(x, y)$. + +We first observe that in \cref{eq:dual_constraints} for any given $i$, the length of $P_i(e_T)$ is always at least $d_\ell(e_T)$ and since all constraints bound $z$ above, we can replace the constraints by \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 \sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T) \qquad \forall i \in \Ih.\\ + \intertext{We can further reduce the constraints to the smallest constraint, again because we are bounding $z$ above.} \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 +Since we are only left with one constraint concerning $z$ and it is not otherwise needed in the dual program we can move it into the objective function and obtain a smaller LP. +While it is no longer of exponential size, it might still take exponential time to find the minimum. \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 +While the non negativity of the distances is actually desired, we now want to show that the last remaining constraint does not in fact reduce the solution space. +Suppose $\sum_{u, v \in V} c_{uv} \ell_{uv} = \beta > 0$, the products of of capacities and lengths sum up to an arbitrary positive value. +We can then transform the set of lengths $\Ell$ to a feasible solution of the dual problem by scaling every length by $\frac{1}{\beta}$. +This, however, changes the objective function by the same factor. +If we drop the constraint enforcing $\beta = 1$, we have to divide the objective function by $\beta$. +This yields a rather compact representation of the dual program. \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