Mercurial > latex

changeset 130:0924abe91f55

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
solve the dual problem
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 20 May 2014 22:09:58 +0200
parents 1b2e38c66a67
children 349d3e5b7973
files minimum_bisection/presentation.tex minimum_bisection/tikzpictures.tex
diffstat 2 files changed, 219 insertions(+), 10 deletions(-) [+]
line wrap: on
line diff
--- 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}
--- 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][]{%