# HG changeset patch # User Markus Kaiser # Date 1400616598 -7200 # Node ID 0924abe91f55fb963f2b4062144f5fe8d525cbb4 # Parent 1b2e38c66a678321404afdc85f0ca0dfcff024e8 solve the dual problem diff -r 1b2e38c66a67 -r 0924abe91f55 minimum_bisection/presentation.tex --- a/minimum_bisection/presentation.tex Tue May 20 18:45:32 2014 +0200 +++ b/minimum_bisection/presentation.tex Tue May 20 22:09:58 2014 +0200 @@ -494,7 +494,6 @@ && \structure{\Ell} &\geq 0 \end{alignat} \end{block} - \todo{Interpretation of $z$ and $\Ell$} \vfill @@ -556,7 +555,7 @@ } \only<3>{% \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}}}\\ + \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}}}\\ \st \quad & \structure{\Ell} \geq 0 \end{alignat} } @@ -581,9 +580,221 @@ \end{frame} \begin{frame} - \frametitle{Polynomial Algorithm} + \frametitle{Tree Metrics} + + \begin{theorem}[Tree Metric] + For our metric $d_\ell$ there exists a \structure{tree metric $(V, M)$} with + \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} \ell_{uv} &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} M_{uv} + \end{alignat} + \endgroup + \end{theorem} + + \vfill + + \centering + \begin{tikzpicture}[grow=down, level distance = 25] + \begin{scope} + \tikzstyle{every node} = [draw, flow node] + \tikzstyle{edge from parent} = [draw, edge] + + \tikzstyle{level 1} = [sibling distance = 100] + \tikzstyle{level 2} = [sibling distance = 50] + \tikzstyle{level 3} = [sibling distance = 30] + \node[label=above:$z$] (z) {} + child { + node[label=above left:$y$] (y) {} + edge from parent + child { + node[label=above left:$x$] (x) {} + edge from parent + child { + node[label=below left:$\structure{u}$] (u) {} + edge from parent + } + child { + node {} + edge from parent + } + } + child { + node {} + edge from parent + child { + node {} + edge from parent + } + child { + node {} + edge from parent + } + } + } + child { + node[label=above right:$\structure{v}$] (v) {} + edge from parent + child { + node {} + edge from parent + child { + node {} + edge from parent + } + child { + node {} + edge from parent + } + } + child { + node {} + edge from parent + child { + node {} + edge from parent + } + child { + node {} + edge from parent + } + } + }; + \end{scope} + + \begin{pgfonlayer}{marked} + \foreach \source/\dest in {u/x,x/y,y/z,z/v} + \draw [tree edge, tumred] (\source.center) -- (\dest.center); + \end{pgfonlayer} + + \node at (0, -3.5) {$T_{uv} = T_{ux} + T_{xy} + T_{yz} + T_{zv}$}; + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Sum over all capacities} + + \begin{lemma}[] + Let $T$ a spanning tree and $(V, M)$ a tree metric of $G = (V, E)$. Then + \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} + + \vfill - content + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges + + \draw + (n) node[above=0.1] {\structure{u}} + (m) node[below] {a} + (e) node[below] {b} + (d) node[above=0.1] {c} + (c) node[below] {d} + (b) node[above=0.1] {\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} + + \only<2> { + \begin{pgfonlayer}{marked} + \draw[tree edge, tumred] (n.center) edge (m.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(n), inner sep=15pt] (el) {}; + \end{pgfonlayer} + } + \only<3> { + \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=3pt] (el) {}; + \end{pgfonlayer} + } + \only<4> { + \begin{pgfonlayer}{marked} + \draw[tree edge, tumred] (e.center) edge (d.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(n)(l)(m)(e)(f), inner sep=3pt] (el) {}; + \end{pgfonlayer} + } + \only<5> { + \begin{pgfonlayer}{marked} + \draw[tree edge, tumred] (d.center) edge (c.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=-10, fit=(c)(b), inner sep=3pt] (el) {}; + \end{pgfonlayer} + } + \only<6> { + \begin{pgfonlayer}{marked} + \draw[tree edge, tumred] (c.center) edge (b.center); + \end{pgfonlayer} + + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, fit=(b), inner sep=15pt] (el) {}; + \end{pgfonlayer} + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Value of the dual problem} + + \begin{block}{Dual Program} + Let $\Ih$ be the exponenitally large set of \structure{all pathtrees}. + \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}}}\\ + \st \quad & \structure{\Ell} \geq 0 + \end{alignat} + \end{block} + + 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{frame} + +\begin{frame} + \frametitle{Value of the primal program} + + \begin{block}{Primal Program} + Let $\Ih$ be the exponenitally large set of \structure{all pathtrees}.\\ + We want to find the best trees with smallest $\alpha$. + \begin{alignat}{3} + \min_{\structure{\alpha, \lambda}} \quad & \mathrlap{\structure{\alpha}}\\ + \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} + \end{block} + + \vfill + + \begin{itemize} + \item There is a $\structure{\lambda}$ such that $\alpha \in \Oh(\log n)$ + \item So out algorithm as an \alert{$\Oh(\log n)$ approximation} + \item But why are polynomially many trees enough? + \end{itemize} \end{frame} \begin{frame} diff -r 1b2e38c66a67 -r 0924abe91f55 minimum_bisection/tikzpictures.tex --- a/minimum_bisection/tikzpictures.tex Tue May 20 18:45:32 2014 +0200 +++ b/minimum_bisection/tikzpictures.tex Tue May 20 22:09:58 2014 +0200 @@ -43,8 +43,8 @@ {(-2,6)/l}, {(-2.5,5)/m}, {(-4,5)/n}} - % \draw \pos\jiggle node[flow node] (\name) {}; - \draw \pos\jiggle node[flow node, label={\name}, font=\footnotesize] (\name) {}; + \draw \pos\jiggle node[flow node] (\name) {}; + % \draw \pos\jiggle node[flow node, label={\name}, font=\footnotesize] (\name) {}; } \newcommand{\flowedges}[1][]{% \foreach \source/\dest in { @@ -76,7 +76,7 @@ {e/g/1/0.7/left}, {n/h/12/0.7/left}, {k/m/5/0.8/right}} - \draw[demand edge, bend \bendage=15] (\source) -- node[flow demand, pos=\pos]{\demand} (\dest); + \draw[demand edge, bend \bendage=15] (\source) edge node[flow demand, pos=\pos]{\demand} (\dest); \end{pgfonlayer} } \newcommand{\flowtreeedges}[1][]{% @@ -87,9 +87,7 @@ {c/d}, {e/d}, {e/f}, {g/i}, {m/e}, {d/k}, {i/j}, {k/j}, {h/i}, {l/m}, {n/m}} - \draw - [tree edge, #1] - (\source.center) -- (\dest.center); + \draw [tree edge, #1] (\source.center) -- (\dest.center); \end{pgfonlayer} } \newcommand{\flowtreeedgestwo}[1][]{%