Mercurial > latex
annotate minimum_bisection/paper/term_paper.tex @ 168:cc6bb3ca79fb default tip
6/4 is not 2
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Fri, 28 Nov 2014 01:41:50 +0100 |
| parents | 8e25d4b73391 |
| children |
| rev | line source |
|---|---|
|
147
faff67582175
add bibliography; append preamble
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
146
diff
changeset
|
1 \input{preamble.tex} |
|
faff67582175
add bibliography; append preamble
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
146
diff
changeset
|
2 \input{tikzpictures.tex} |
| 146 | 3 |
|
147
faff67582175
add bibliography; append preamble
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
146
diff
changeset
|
4 \title{Oblivious Routing and Minimum Bisection} |
|
faff67582175
add bibliography; append preamble
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
146
diff
changeset
|
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} |
| 146 | 6 \institute{Technische Universit\"at M\"unchen\\ |
| 163 | 7 \email{\href{mailto:markus.kaiser@in.tum.de}{markus.kaiser@in.tum.de}}} |
| 146 | 8 |
| 9 \begin{document} | |
| 10 | |
| 11 \maketitle | |
| 148 | 12 \thispagestyle{plain} |
| 146 | 13 \begin{abstract} |
| 158 | 14 Oblivious routing is generalization of multi commodity flows where the actual demand function is unknown. |
| 156 | 15 This paper proofs the existence of an approximate solution using tree metrics which can easily be transformed into an $\Oh(\log n)$ approximation algorithm. |
| 158 | 16 This result is then applied to the minimum bisection problem asking for an vertex bisection with minimal cost in the edges between the sets, also resulting in an $\Oh(\log n)$ approximation. |
| 146 | 17 \end{abstract} |
| 18 | |
| 148 | 19 \section{Oblivious Routing} |
| 20 \label{sec:oblivious_routing} | |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
21 |
| 158 | 22 \define{Maximum flow} is a well understood algorithmic problem. |
| 160 | 23 Given a directed graph $G = (V, E)$, a mapping $c : E \to \Rnn$ denoted by $c_e \defeq c(e)$ assigning a maximum non-negative capacity to every edge and a \define{source} and \define{target} node $s, t \in V$, we are asked to find a flow of maximum value from $s$ to $t$. |
|
151
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
24 For simplicity, we assume that $G$ is complete, which can be achieved by adding edges of capacity $0$. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
25 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
26 \begin{definition}[Flow \cite{intro}] |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
27 A function $f : E \to \Rnn$ assigning a throughput to every edge. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
28 It satisfies the following two properties: |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
29 \begin{description} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
30 \item[Capacity Constraint:] For all $e \in E$, we have $f_e \leq c_e$. |
|
157
33290e7a43e4
fix bisection picture
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
156
diff
changeset
|
31 \item[Flow Conservation:] For all $v \in V \setminus \left\{ s, t \right\}$, we have |
|
151
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
32 \[\sum_{(u, v) \in E} f_{uv} = \sum_{(v, w) \in E} f_{vw}.\] |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
33 \end{description} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
34 We denote $f_e \defeq f(e)$ for $e \in E$ and $f_{uv} \defeq f(u, v)$ for $u, v \in V$. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
35 \end{definition} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
36 |
| 158 | 37 The maximum flow problem can be solved in polynomial time using a number of algorithms, for example the Ford-Fulkerson method or Push-relabel algorithms, both of which are described in \cite{intro}. |
|
151
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
38 |
| 158 | 39 This paper will introduce a generalization of this problem known as \define{oblivious routing} and proof the existence of an $\Oh(\log n)$ approximation algorithm based on \cite{racke2008optimal} and described in \cite{approx}. |
|
151
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
40 After giving a definition of the problem, it is formulated as a linear problem and rewritten to yield the desired algorithm using a theorem giving an $\Oh(\log n)$ approximation of arbitrary metrics using tree metrics. |
| 158 | 41 Finally, the result is applied to give an $\Oh(\log n)$ approximation of the \define{minimum bisection} problem. |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
42 |
| 148 | 43 \subsection{Problem definition} |
| 44 \label{sub:or_problem} | |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
45 |
| 148 | 46 \begin{figure}[tb] |
| 47 \centering | |
| 48 \begin{tikzpicture}[flow graph] | |
| 49 \path[use as bounding box] (-4, 2.4) rectangle (3.5,6.15); | |
| 50 \flownodes | |
| 51 \flowedges | |
| 52 | |
| 53 \draw | |
| 54 (n) node[below=3] {\structure{u}} | |
| 55 (j) node[below=3] {\structure{v}}; | |
| 56 | |
| 57 \begin{pgfonlayer}{demand} | |
| 58 \draw[demand edge, bend left=20] (n) edge (j); | |
| 59 \end{pgfonlayer} | |
| 60 | |
| 61 \begin{pgfonlayer}{marked} | |
| 62 \draw[marked edge, tumgreen] | |
| 63 (n.center) edge (l.center) | |
| 64 (l.center) edge (h.center) | |
| 65 (h.center) edge (i.center) | |
| 66 (i.center) edge (j.center); | |
| 67 | |
| 68 \draw[marked edge, tumblue] | |
| 69 (n.center) edge (m.center) | |
| 70 (m.center) edge (e.center) | |
| 71 (e.center) edge (c.center) | |
| 72 (c.center) edge (k.center) | |
| 73 (k.center) edge (j.center); | |
| 74 | |
| 75 \draw[marked edge, tumred] | |
| 76 (n.center) edge (b.center) | |
| 77 (b.center) edge (j.center); | |
| 78 \end{pgfonlayer} | |
| 79 | |
| 80 \node at (-0.25, 2.4) {$\lambda_{green} = 0.25 \qquad \lambda_{blue} = 0.5 \qquad \lambda_{red} = 0.25$}; | |
| 81 \end{tikzpicture} | |
| 160 | 82 \caption{A solution to the oblivious routing problem gives a set of paths and an associated convex combination for any two nodes $u, v \in V$. In this case, we are given the green, blue and red paths from $u$ to $v$. The dashed demand $d_{uv}$ gets routed along these three paths, split according to the factors $\lambda_i$.} |
| 148 | 83 \label{fig:oblivous_routing} |
| 84 \end{figure} | |
| 85 | |
| 158 | 86 To define oblivious routing, we first consider a simpler generalization of maximum flow, the \define{multi-commodity flow} problem. |
| 160 | 87 Instead of a single source and target node, we now allow an arbitrary number of nonnegative flow demands between two nodes given by a \define{demand function $d : V^2 \to \Rnn$} on an undirected graph. |
| 88 Every such demand $d_{uv}$ must be routed from $u$ to $v$ using a set of $u$-$v$-paths and the total flow $f_e$ on an edge $e \in E$ is the sum of all demands routed through it. | |
|
151
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
89 The task of is now to find a flow satisfying all demands while exceeding the capacities of all edges as little as possible. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
90 This excess is called \define{congestion}. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
91 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
92 \begin{definition}[Congestion] |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
93 The congestion $\rho$ attributed to a flow $f$ denotes the smallest factor $\rho$ such that for all edges $e \in E$ we have $f_e \leq \rho \cdot c_e$. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
94 \begin{align} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
95 \rho = \max_{e \in E} \frac{f_e}{c_e} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
96 \end{align} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
97 \end{definition} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
98 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
99 This problem is still solvable in polynomial time using linear programming \cite{approx}. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
100 One more generalization leads to the oblivious routing problem. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
101 We now want to find flow solutions without knowing the demands beforehand, i.e. we want to find a set of $u$-$v$-paths and associated fractions of demands for all $u, v \in V$ such that for any demand function this set of paths performs well. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
102 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
103 \begin{problem}[Oblivious Routing] |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
104 Given an undirected Graph $G = (V, E)$ and an edge capacity function $c : E \to \R^+$. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
105 Calculate a convex combination of paths for each $(u, v) \in V^2$ such that for any demand function the congestion of the resulting flow will be as small as possible. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
106 \end{problem} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
107 |
| 148 | 108 \subsection{Formulation as a linear program} |
| 109 \label{sub:or_lp} | |
|
151
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
110 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
111 \begin{figure}[tb] |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
112 \centering |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
113 \begin{tikzpicture}[flow graph] |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
114 \flownodes |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
115 \flowedges |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
116 \flowtreeedges |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
117 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
118 \begin{pgfonlayer}{background} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
119 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=8pt] (el) {}; |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
120 \end{pgfonlayer} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
121 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
122 \path (el) |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
123 ++ (200:1) |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
124 ++ (0, -0.5) coordinate (label); |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
125 \node[below of = label] {\structure{$S(\alert{e_T})$}}; |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
126 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
127 \begin{pgfonlayer}{marked} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
128 \foreach \source/ \dest in {l/h,m/e,m/f,n/b} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
129 \draw[tree edge, tumorange] (\source.center) edge (\dest.center); |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
130 \end{pgfonlayer} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
131 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
132 \begin{pgfonlayer}{marked} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
133 \draw[tree edge, tumblue] (m.center) edge (e.center); |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
134 \end{pgfonlayer} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
135 \path (m) -- node[flow capacity]{$e_T$} (e); |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
136 \end{tikzpicture} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
137 |
| 160 | 138 \caption{Removing the edge $e_T$ from the green spanning tree introduces a tree split. One of the two vertex sets we denote as $S(e_T)$ and define the capacity of the split as the sum of all capacities of edges crossing the boundary of $S(e_T)$, the blue and orange edges.} |
|
151
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
139 \label{fig:tree_splits} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
140 \end{figure} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
141 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
142 To find the desired approximation algorithm, we must first develop some lower bound for the optimal solution. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
143 A simple idea to create a valid (but probably not optimal) solution is to find any spanning tree $T = (V, E_T)$ of $G$ and route any demand along its edges. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
144 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
145 Since it is a spanning tree, there is a unique path from any vertex $u$ to any vertex $v$ in $T$ which will be used to satisfy the complete demand. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
146 For any edge $e_T \in E_T$ the resulting flow $f_{e_T}$ will be the sum of all demands between two nodes connected by this tree edge. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
147 These are exactly the nodes in different connected components created by removing the edge $e_T$. |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
148 |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
149 \begin{definition}[Tree Split] |
|
151
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
150 Given a tree $T = (V, E_T)$ and an edge $e_T \in E_T$. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
151 Removing $e_T$ from $T$ splits it into two connected components, one of which we call $S(e_T)$ and the other one being $V \setminus S(e_T)$. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
152 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
153 We call $C(e_T)$ the capacity and $D(e_T)$ the demand of this split given by the sum of all capacities and demands connecting nodes in different connected components. |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
154 \begin{align} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
155 C(e_T) &= \sum_{\substack{u \in S(e_T), \\ v \not\in S(e_T)}} c_{uv}\\ |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
156 D(e_T) &= \sum_{\substack{u \in S(e_T), \\ v \not\in S(e_T)}} c_{uv} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
157 \end{align} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
158 \end{definition} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
159 |
| 160 | 160 This definition illustrated by \cref{fig:tree_splits} allows us to write the flow generated by a simple solution to oblivious routing using a spanning tree $T$ as $f_{e_T} = D(e_T)$ for all $e_T \in T$ and $0$ otherwise. We now observe that for a given demand function any solution to the resulting multi-commodity flow problem will be bounded below by all tree splits. |
|
151
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
161 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
162 \begin{lemma} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
163 \label{lem:optimal} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
164 For any tree $T$ and any tree edge $e_T$, any routing in $G$ must contain an edge $e$ with congestion |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
165 \begin{align} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
166 \rho_e \geq \frac{D(e_T)}{C(e_T)}. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
167 \end{align} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
168 Therefore, the optimal congestion $\rho^\ast$ of the flow problem can be no better. |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
169 \end{lemma} |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
170 |
|
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
171 We will use this observation to proof our approximation guarantee. |
| 152 | 172 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$. |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
173 \begin{align} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
174 \forall e_T \in E_T.\quad c_{e_T} &\geq \frac{1}{\alpha} C(e_T) |
|
151
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
175 \intertext{Using \cref{lem:optimal} we can bound the congestion of this spanning tree in relation to the optimal solution.} |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
176 \structure{\rho_T} &= \max_{e_T} \frac{D(e_T)}{c_{e_T}}\\ |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
177 &\structure{\leq} \alpha \max_{e_T} \frac{D(e_T)}{C(e_T)}\\ |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
178 &\leq \structure{\alpha \rho^\ast} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
179 \end{align} |
|
151
59e62bb8c8dd
first part of the paper
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
150
diff
changeset
|
180 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. |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
181 |
| 160 | 182 This tree however does not have to exist and therefore this approach will not yield any approximation guarantee. |
| 152 | 183 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. |
| 184 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. | |
| 185 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$. | |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
186 |
| 152 | 187 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. |
| 188 For every edge $e$ in the original graph we get | |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
189 \begin{align} |
| 152 | 190 f_e &= \sum_{\substack{i:\\e \in T_i}} \lambda_i D_i(e) |
| 191 \end{align} | |
| 192 where we denote the demand of the split introduced by $T_i$ using some edge $e \in T_i$ as $D_i(e)$. | |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
193 |
| 152 | 194 This solution scheme is still too strict though and we want to allow more sophisticated structures. |
| 195 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$. | |
| 196 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$. | |
| 197 A pair of spanning tree and set of paths connecting two neighboured nodes in the tree is called a path tree. | |
| 148 | 198 |
| 199 \begin{figure}[tb] | |
| 200 \centering | |
| 201 \begin{tikzpicture}[flow graph] | |
| 202 \flownodes | |
| 203 \flowedges | |
| 204 | |
| 205 \draw | |
| 206 (l) node[above=3] {\structure{u}} | |
| 207 (i) node[above=3] {\structure{v}} | |
| 208 (e) node[above left] {\structure{x}} | |
| 209 (d) node[above=3] {\structure{z}} | |
| 210 (c) node[below=3] {\structure{y}} ; | |
| 211 | |
| 212 \begin{pgfonlayer}{demand} | |
| 213 \draw[demand edge, bend left=10] (l) edge (i); | |
| 214 \end{pgfonlayer} | |
| 215 | |
| 216 \begin{pgfonlayer}{marked} | |
| 217 \foreach \source/ \dest in {l/m,m/e,d/k,k/j,j/i} | |
| 218 \draw[tree edge, tumgreen] (\source.center) edge (\dest.center); | |
| 219 \end{pgfonlayer} | |
| 220 | |
| 221 \begin{pgfonlayer}{marked} | |
| 222 \draw[tree edge, line width=4pt, white] (e.center) edge (d.center); | |
| 223 \draw[tree edge, densely dashed, tumgreen!80] (e.center) edge (d.center); | |
| 224 | |
| 225 \foreach \source/\dest in {e/c,c/d} | |
| 226 \draw[tree edge, tumblue!80] (\source.center) edge (\dest.center); | |
| 227 \end{pgfonlayer} | |
| 228 | |
| 152 | 229 % \begin{pgfonlayer}{marked} |
| 230 % \foreach \source/ \dest in {l/h,h/i} | |
| 231 % \draw[tree edge, tumorange] (\source.center) edge (\dest.center); | |
| 232 % \end{pgfonlayer} | |
| 148 | 233 \end{tikzpicture} |
| 152 | 234 \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))$.} |
| 148 | 235 \label{fig:pathtrees} |
| 236 \end{figure} | |
| 237 | |
| 152 | 238 \begin{definition}[Path Tree] |
| 239 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$. | |
| 240 \end{definition} | |
| 241 | |
| 242 Note that the same edge in $G$ may well be used by multiple different paths in the same path tree. | |
| 243 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. | |
| 244 | |
| 245 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)$. | |
| 246 If we now consider a convex combination of path trees, the flow through every edge $e \in E$ is | |
| 247 \begin{align} | |
| 248 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}). | |
| 249 \end{align} | |
| 250 | |
| 154 | 251 Suppose we find a set of path trees such that |
| 152 | 252 \begin{align} |
| 253 \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}) | |
|
153
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
254 \intertext{we can again bound its congestion by the optimal solution using \cref{lem:optimal}.} |
| 152 | 255 \rho &= \hphantom{\alpha}\max_{\structure{e}} \frac{f_e}{c_{\structure{e}}} \\ |
| 256 &\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})} \\ | |
| 257 &\leq \alpha \max_{\structure{e}} \max_{i} \frac{D_i(\structure{e})}{C_i(\structure{e})} \leq \alpha \rho^\ast | |
| 258 \end{align} | |
| 259 | |
| 260 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. | |
| 261 We denote the finite but exponentially sized set of all path trees over $G$ as $\Ih$. | |
| 262 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. | |
| 148 | 263 \begin{alignat}{3} |
| 264 \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}} \label{eq:primal}\\ | |
| 265 \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 \\ | |
| 266 && \sum_{i \in \Ih} \structure{\lambda_i} &= 1 \\ | |
| 267 && \structure{\lambda} &\geq 0 | |
| 268 \end{alignat} | |
| 269 | |
| 152 | 270 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. |
| 271 | |
| 148 | 272 \subsection{Approximation guarantee using the dual} |
| 273 \label{sub:or_approx} | |
| 274 | |
| 152 | 275 To proof the bound for the value of the linear program, we will consider the dual program and show that it is logarithmically bounded. |
| 160 | 276 The dual problem has exponentially many constraints, one for each path tree, and a decision variable $\ell_{uv} \in \Ell$ for every pair of vertices. |
| 148 | 277 \begin{alignat}{3} |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
278 \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}} \label{eq:dual}\\ % |
| 148 | 279 \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\ |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
280 && \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}\\ |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
281 && \structure{\Ell} &\geq 0 |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
282 \end{alignat} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
283 |
| 152 | 284 We will rewrite this dual program to be able to apply a result about the approximation of metrics with tree metrics. |
| 160 | 285 To this end we will interpret the variables $\ell_{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)$. |
| 152 | 286 |
| 160 | 287 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 and there is some tree choosing the shortest path, we can replace the constraints by |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
288 \begin{align} |
| 152 | 289 \structure{z} & \leq \sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T) \qquad \forall i \in \Ih.\\ |
| 290 \intertext{We can further reduce the constraints to the smallest constraint, again because we are bounding $z$ above.} | |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
291 \structure{z} & \leq \min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T) |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
292 \end{align} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
293 |
| 152 | 294 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. |
| 295 While it is no longer of exponential size, it might still take exponential time to find the minimum. | |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
296 \begin{alignat}{3} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
297 \max_{\structure{\Ell}} \quad & \mathrlap{\min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)}\\ |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
298 \st \quad && \tikzmark{a}\sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1\tikzmark{b} \\ |
| 148 | 299 && \structure{\Ell} &\geq 0 |
| 300 \end{alignat} | |
| 301 | |
| 160 | 302 While the nonnegativity of the distances is actually desired, we now want to show that the last remaining constraint does not in fact reduce the solution space. |
| 152 | 303 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. |
| 304 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}$. | |
| 305 This, however, changes the objective function by the same factor. | |
| 306 If we drop the constraint enforcing $\beta = 1$, we have to divide the objective function by $\beta$. | |
| 307 This yields a rather compact representation of the dual program. | |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
308 \begin{alignat}{3} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
309 \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}\\ |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
310 \st \quad & \structure{\Ell} \geq 0 |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
311 \end{alignat} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
312 |
| 148 | 313 \begin{figure}[tb] |
| 314 \centering | |
| 315 \begin{tikzpicture}[flow graph] | |
| 316 \flownodes | |
| 317 \flowedges | |
| 318 \flowtreeedges | |
| 319 | |
| 320 \draw | |
| 321 (n) node[above=3] {\structure{u}} | |
| 322 (m) node[below=3] {a} | |
| 323 (e) node[below=3] {b} | |
| 324 (d) node[above=3] {c} | |
| 325 (c) node[below=3] {d} | |
| 326 (b) node[below=3] {\structure{v}}; | |
| 327 | |
| 328 \path | |
| 329 (n) -- node[node on edge] {$c_{uv}$} (b); | |
| 330 | |
| 331 \begin{pgfonlayer}{marked} | |
| 332 \draw[tree edge, tumorange] (n.center) edge (b.center); | |
| 333 \end{pgfonlayer} | |
| 334 | |
| 335 \begin{pgfonlayer}{marked} | |
| 336 \draw[tree edge, tumred] (m.center) edge (e.center); | |
| 337 \end{pgfonlayer} | |
| 338 | |
| 339 \begin{pgfonlayer}{background} | |
| 340 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m), inner sep=8pt] (el) {}; | |
| 341 \end{pgfonlayer} | |
| 342 \end{tikzpicture} | |
|
155
b7fd203d37d8
finish minimum bisection
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
154
diff
changeset
|
343 \caption{The left hand side contains a product of capacity $c_{uv}$ and distance $M_{ab}$ iff $c_{uv}$ is part of the tree split introduced by the tree edge $(a, b)$. A capacity is part of a tree split iff $u$ and $v$ are not in the same connected component in the split. This is the case iff the tree edge lies on the path between $u$ and $v$. The sum of all tree edges between $u$ and $v$ is $M_{uv}$ by definition, yielding the right hand side of the sum.} |
| 148 | 344 \label{fig:sum_over_capacities} |
| 345 \end{figure} | |
| 346 | |
|
153
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
347 To proof the desired approximation guarantee we now approximate $d_\ell$ using a result obtained about tree metrics from \cite{approx}. |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
348 \begin{theorem}[Tree Metric] |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
349 For any nonnegative set of costs $c_{uv}$ and any metric $d_\ell$ there exists a tree metric $(V, M)$ such that |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
350 \begingroup |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
351 \addtolength{\jot}{.5em} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
352 \begin{alignat}{2} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
353 d_\ell(u, v) &\leq M_{uv} & \forall u, v \in V\\ |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
354 \sum_{u, v \in V} c_{uv} M_{uv} &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v). |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
355 \end{alignat} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
356 \endgroup |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
357 \end{theorem} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
358 |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
359 To be able to apply this result to our dual, we first need to show one more lemma. |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
360 We need to rewrite the enumerator in \cref{eq:dual_compact} to not sum over tree edges but all edges in the graph. |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
361 \begin{lemma} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
362 Let $T$ be a spanning tree and $(V, M)$ a tree metric of $G = (V, E)$. |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
363 Then it holds that |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
364 \begin{align} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
365 \sum_{(x, y) \in E_T} C(x, y) M_{xy} = \sum_{(u, v) \in E} c_{uv} M_{uv}. |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
366 \end{align} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
367 \end{lemma} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
368 \begin{proof} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
369 See \cref{fig:sum_over_capacities}. |
| 160 | 370 \qed |
|
153
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
371 \end{proof} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
372 |
|
157
33290e7a43e4
fix bisection picture
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
156
diff
changeset
|
373 Combining all observations and lemmas now bounds the value of both linear programs logarithmically, directly following from the logarithmic bound of the tree metrics. |
|
155
b7fd203d37d8
finish minimum bisection
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
154
diff
changeset
|
374 |
| 160 | 375 \begin{theorem} |
|
155
b7fd203d37d8
finish minimum bisection
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
154
diff
changeset
|
376 The primal and dual linear program have a value of $\Oh(\log n)$. |
| 160 | 377 \end{theorem} |
|
153
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
378 \begin{proof} |
|
155
b7fd203d37d8
finish minimum bisection
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
154
diff
changeset
|
379 We proof the value of the dual program, the value of the primal program then follows by strong duality. |
|
b7fd203d37d8
finish minimum bisection
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
154
diff
changeset
|
380 |
| 160 | 381 For any lengths $\Ell$ we know that for the minimizing tree in \cref{eq:dual_compact} we have the following chain of inequalities, using the definition of tree metrics, the previous lemma and the observation that the distance $d_\ell(u, v)$ is never larger than $\ell_{uv}$ since $d_\ell$ is a shortest path metric. |
|
153
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
382 \begin{align} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
383 \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} \\ |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
384 &= \sum_{u, v \in V} c_{uv} M_{uv} \\ |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
385 &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v) \\ |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
386 &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} \ell_{uv} \\ |
|
155
b7fd203d37d8
finish minimum bisection
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
154
diff
changeset
|
387 \intertext{Dividing by the sum directly gives the value guarantee:} |
|
153
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
388 \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) |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
389 \end{align} |
| 160 | 390 \qed |
|
153
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
391 \end{proof} |
|
c02cfd41bcc4
remove one approximation
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
152
diff
changeset
|
392 |
| 160 | 393 While this proofs the existence of a solution of value $\Oh(\log n)$, it still remains to be shown that polynomially many trees are enough and the solution can actually be found in polynomial time. |
|
155
b7fd203d37d8
finish minimum bisection
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
154
diff
changeset
|
394 While this is done rigorously in \cite{approx}, the idea is to rewrite the linear program in such a way to not actually search for the minimal $\alpha$ but enforce an $\alpha \in \Oh(\log n)$. |
|
b7fd203d37d8
finish minimum bisection
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
154
diff
changeset
|
395 This results in a linear program which can be solved using the ellipsoid method in polynomial time resulting in a set of polynomially many path trees. |
|
b7fd203d37d8
finish minimum bisection
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
154
diff
changeset
|
396 This then proofs the existence of the desired $\Oh(\log n)$ approximation algorithm. |
|
b7fd203d37d8
finish minimum bisection
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
154
diff
changeset
|
397 |
| 148 | 398 \section{Minimum Bisection} |
| 399 \label{sec:minimum_bisection} | |
|
157
33290e7a43e4
fix bisection picture
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
156
diff
changeset
|
400 |
| 148 | 401 \begin{figure}[tb] |
| 402 \centering | |
| 403 \begin{tikzpicture}[flow graph] | |
| 404 \flownodes | |
| 405 \flowedges | |
| 406 | |
| 407 \begin{pgfonlayer}{background} | |
|
157
33290e7a43e4
fix bisection picture
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
156
diff
changeset
|
408 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(n)(l)(m)(h)(e)(f), rotate=10, inner sep=-8pt] (el) {}; |
| 148 | 409 \end{pgfonlayer} |
| 410 | |
| 411 \path (el) | |
|
157
33290e7a43e4
fix bisection picture
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
156
diff
changeset
|
412 ++ (-120:2.1) node {\structure{$S$}}; |
| 148 | 413 |
| 414 \begin{pgfonlayer}{marked} | |
|
157
33290e7a43e4
fix bisection picture
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
156
diff
changeset
|
415 \foreach \source/\dest in {n/b,f/b,f/c,e/c,e/d,e/g,h/i} |
| 148 | 416 \draw [tree edge, tumorange] (\source.center) -- (\dest.center); |
| 417 \end{pgfonlayer} | |
| 418 \end{tikzpicture} | |
| 159 | 419 \caption{The cost $c(\delta(S))$ of the bisection $S$ is defined as the sum of the nonnegative costs of all orange edges leaving the set $S$.} |
| 148 | 420 \label{fig:minimum_bisection} |
| 421 \end{figure} | |
| 422 | |
| 159 | 423 The knowledge about the existence of an $\Oh(\log n)$ approximation algorithm for the oblivious routing problem can be applied to find approximation algorithms for a number of other problems, some of which are described in \cite{racke2008optimal}. |
| 424 As an example, we will now give a definition of the minimum bisection problem and show that it can be approximated using oblivious flow. | |
| 425 | |
| 426 Minimum bisection has a similar structure to oblivious flow as it is also defined over undirected graphs with a function mapping the edges to non negative numbers. | |
| 427 Instead of interpreting these numbers as a capacity, they are now understood as costs. | |
| 428 We want to find a set containing half of the vertices such that the sum of all costs of edges leaving this set is minimal. | |
| 429 \begin{problem}[Minimum Bisection] | |
| 430 Given an undirected Graph $G = (V, E)$ and an edge-cost function $c : E \to \Rnn$. | |
| 431 Find a set $S \subset V$ containing half the vertices with minimal split cost $c(\delta(S))$. | |
| 432 \begin{align} | |
| 433 \delta(S) &\defeq \left\{ (x, y) \in E \mid x \in S \wedge y \not\in S \right\} \\ | |
| 434 c(\delta(S)) &\defeq \sum_{\substack{e \in E:\\e \in \delta(S)}} c_e | |
| 435 \end{align} | |
| 436 \end{problem} | |
| 437 | |
| 438 We will now show that the set of path trees obtained by solving the oblivious flow problem on $G$ with capacity function $c$ contains a tree that defines a bisection of $G$ which costs logarithmically more than an optimal solution. | |
| 160 | 439 We call this bisection a minimum tree bisection. |
| 159 | 440 It is obtained by reweighing the edges of the tree to cost as much as the tree splits introduced by them and then solving the minimum bisection problem on those trees. |
| 441 This can be solved in polynomial time with a straightforward dynamic programming approach described in \cite{approx}. | |
| 442 | |
| 443 \begin{definition}[Minimum Tree Bisection] | |
| 444 Given a spanning tree $T$ of $G$ with an edge $e_T \in E_T$. | |
| 445 We define a new cost function $c_T : E_T \to \Rnn$ based on the tree splits induced by the edges of $T$. | |
| 446 The cost of a bisection $S$ is the sum of tree split costs of all tree edges cut by $S$. | |
| 447 \begin{align} | |
| 448 c_T(e_T) &= C(e_T)\\ | |
| 449 c_T(\delta(S)) &= \sum_{\substack{e_T \in E_T:\\e_T \in \delta(S)}} C(e_T) | |
| 450 \end{align} | |
| 451 The minimum tree bisection $X$ of $T$ is an optimal solution of the minimum bisection problem with respect to the cost function $c_T$. | |
| 452 \end{definition} | |
| 453 | |
| 454 Assuming we can find minimum tree bisections in polynomial time, the following algorithm describes an $\Oh(\log n)$ approximation algorithm for the minimum bisection problem. | |
| 455 While the polynomial running time is clear, it remains to show that the obtained solution actually satisfies the approximation guarantee. | |
| 456 | |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
457 \begin{algorithm} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
458 \label{alg:minimum_bisection} |
|
157
33290e7a43e4
fix bisection picture
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
156
diff
changeset
|
459 Given graph $G = (V, E)$ and cost function $c : E \to \Rnn$. |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
460 \begin{enumerate} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
461 \item Interpret costs $c(e)$ as capacities |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
462 \item Solve oblivious routing on $G$, obtaining trees $T_i$ |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
463 \item Find minimum tree bisections $X_i$ for all trees $T_i$ |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
464 \item Choose the $X_i$ with lowest $c(\delta(X_i))$ |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
465 \end{enumerate} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
466 \end{algorithm} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
467 |
| 159 | 468 To proof the guarantee we will need two lemmas connecting the cost of a split in the original graph $G$ with the costs in a single spanning tree $T$ relative to its cost function $c_T$ and a convex combination of trees. |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
469 |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
470 \begin{lemma} |
| 159 | 471 \label{lem:bisection_combination} |
| 472 Let $\left\{ (T_i, \lambda_i) \right\}$ be an $\Oh(\log n)$-approximation to the oblivious flow problem. | |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
473 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. |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
474 \begin{align} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
475 \sum_i \lambda_i c_{T_i}(\delta(S)) \leq \Oh(\log n) c(\delta(S)) |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
476 \end{align} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
477 \end{lemma} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
478 \begin{proof} |
| 159 | 479 We remember the first constraint of the primal program in \cref{eq:primal}. |
| 480 Since we have already proven that $\alpha \in \Oh(\log n)$ we can replace it by this bound and sum up the inequalities for all edges in $\delta(S)$. | |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
481 \begin{align} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
482 \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)) |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
483 \end{align} |
| 159 | 484 The right hand side then sums up to the desired term, while we have to rewrite the left hand side a bit. |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
485 \begin{align} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
486 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) |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
487 \end{align} |
| 159 | 488 While the equality holds by definition, we observe that for every tree edge $e_T$ contained in $\delta(S)$ there must be an edge in $P_i(e_T)$ which crosses the boundary of $S$ since $e_T$ starts in $S$ and ends outside of $S$. |
| 489 Therefore, all summands in the left side are contained in the right side, the inequality holds. | |
| 490 If we apply this for all $T_i$, we have proven the lemma. | |
| 160 | 491 \qed |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
492 \end{proof} |
|
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
493 |
| 159 | 494 While we can bound the convex combination of minimum tree bisections obtained by the oblivious flow approximation by the original cost function, we can also show that the original cost is always smaller than the cost of the same set relative to some tree cost function. |
|
150
8c10f9532afc
add most of the math
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
149
diff
changeset
|
495 |
| 148 | 496 \begin{figure}[tb] |
| 497 \begin{tikzpicture}[flow graph] | |
| 498 \flownodes | |
| 499 \flowedges | |
| 500 \flowtreeedges | |
| 501 | |
| 502 \begin{pgfonlayer}{background} | |
| 503 \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(c)(d)(g)(k)(j)(i)(e)(h), inner sep=3pt] (el) {}; | |
| 504 \end{pgfonlayer} | |
| 505 | |
| 506 \path (el) | |
| 507 ++ (-30:2.6) node {\structure{$S$}}; | |
| 508 | |
| 509 \draw | |
| 510 (b) node[below=3] {\structure{u}} | |
| 511 (j) node[below=3] {\structure{v}}; | |
| 512 | |
| 513 \begin{pgfonlayer}{marked} | |
| 514 \foreach \source/\dest in {f/c,b/j,l/h} | |
| 515 \draw [tree edge, tumblue, dash pattern=on 7pt off 7pt] (\source.center) -- (\dest.center); | |
| 516 | |
| 517 \foreach \source/\dest in {b/c,e/f,e/m} | |
| 518 \draw [tree edge, tumred] (\source.center) -- (\dest.center); | |
| 519 \end{pgfonlayer} | |
| 520 | |
| 521 \foreach \source/\dest/\name in {b/c/$e_3$,e/f/$e_2$,e/m/$e_1$} | |
| 522 \path (\source) -- node[node on edge] {\name} (\dest); | |
| 523 \end{tikzpicture} | |
| 159 | 524 \caption{The cost of $S$ in the original graph is the sum of all red and blue dashed edge costs. While the red edges are tree edges and thus contained in the tree cost function, the blue dashed edge connecting $u$ and $v$ is contained in the tree split introduced by edge $e_3$ on the tree path between $u$ and $v$.} |
| 148 | 525 \label{fig:tree_bisections} |
| 526 \end{figure} | |
| 527 | |
| 159 | 528 \begin{lemma} |
| 529 \label{lem:bisection_single} | |
| 530 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$. | |
| 531 \begin{align} | |
| 532 c(\delta(S)) \leq c_T(\delta(S)) | |
| 533 \end{align} | |
| 534 \end{lemma} | |
| 535 \begin{proof} | |
| 536 An edge $(u, v)$ is contained in $\delta(S)$ iff it starts in $S$ and ends outside of $S$. | |
| 537 Since there is an unique path from $u$ to $v$ in $T$ there must be an edge $e_T$ on this path that is also contained in $\delta(S)$. | |
| 538 But then $(u, v)$ must be contained in the tree split introduced by $e_T$ and is therefore contained in the right hand side costs by definition. | |
| 539 See \cref{fig:tree_bisections} for an illustration of this proof. | |
| 160 | 540 \qed |
| 159 | 541 \end{proof} |
| 542 | |
| 543 These lemmas allow us to quickly prove the approximation guarantee of the algorithm. | |
| 544 | |
| 545 \begin{theorem} | |
| 546 \cref{alg:minimum_bisection} is an $\Oh(\log n)$ approximation algorithm for the minimum bisection problem. | |
| 547 \end{theorem} | |
| 548 \begin{proof} | |
| 549 Let $X^\ast$ be an optimal minimum bisection of $G$ and $\left\{ (T_i, \lambda_i) \right\}$ be a set of trees obtained from the oblivious flow algorithm with minimum tree bisections $X_i$. | |
| 550 We consider the convex combination of the costs of all minimum tree bisections. | |
| 551 \begin{align} | |
| 552 \sum_i \lambda_i c(\delta(X_i)) &\leq \sum_i \lambda_i c_{T_i}(\delta(X_i)) \\ | |
| 553 &\leq \sum_i \lambda_i c_{T_i}(\delta(X^\ast) \\ | |
| 554 &\leq \Oh(\log n) c(\delta(X^\ast)) | |
| 555 \end{align} | |
| 556 Using \cref{lem:bisection_single} we know that every single tree bisection $X_i$ can only cost more relative to its respective cost function $c_{T_i}$. | |
| 557 But since the $X_i$ are optimal solutions for the trees $T_i$, the global optimal solution $X^\ast$ cannot be better. | |
| 558 We now apply \cref{lem:bisection_combination} to show that the original convex combination of bisections is bounded by our desired bound. | |
| 559 Since the combination of nonnegative costs is bounded, so must be the smallest cost or otherwise the inequality cannot hold. | |
| 560 This proofs the correctness of the algorithm. | |
| 160 | 561 \qed |
| 159 | 562 \end{proof} |
| 563 | |
|
147
faff67582175
add bibliography; append preamble
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
146
diff
changeset
|
564 \nocite{*} |
| 146 | 565 \bibliographystyle{alpha} |
|
147
faff67582175
add bibliography; append preamble
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
146
diff
changeset
|
566 \bibliography{term_paper} |
| 146 | 567 \end{document} |