# HG changeset patch # User Markus Kaiser # Date 1400604332 -7200 # Node ID 1b2e38c66a678321404afdc85f0ca0dfcff024e8 # Parent f753b74f0e72099ed2196dcbdab79ca3c68b697c dual conversion diff -r f753b74f0e72 -r 1b2e38c66a67 minimum_bisection/presentation.tex --- a/minimum_bisection/presentation.tex Mon May 19 13:37:32 2014 +0200 +++ b/minimum_bisection/presentation.tex Tue May 20 18:45:32 2014 +0200 @@ -445,9 +445,9 @@ \begingroup \addtolength{\jot}{.5em} \begin{align} - \structure{\rho} &= \hphantom{\alpha}\max_{\structure{e}} \frac{f(\structure{e})}{c_{\structure{e}}} \\ - &\structure{\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 \structure{\alpha \rho^\ast} + \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} \endgroup \end{itemize} @@ -462,39 +462,122 @@ \end{frame} \begin{frame} - \frametitle{Primal Program} + \frametitle{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 \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}} & \quad \forall \alert{u,v} \in V \\ - && \sum_i \structure{\lambda_i} &= 1 \\ + \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{center} + We want to show that $\alpha \in \Oh(\log n)$ + \end{center} +\end{frame} + +\begin{frame} + \frametitle{Dual program} + + \begin{block}{Dual Program} + Let $\Ih$ be the exponenitally large set of \structure{all pathtrees}. + \begin{alignat}{3} + \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ % + \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\ + && \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 \\ + && \structure{\Ell} &\geq 0 + \end{alignat} + \end{block} + \todo{Interpretation of $z$ and $\Ell$} + + \vfill + + \begin{center} + If $z \in \Oh(\log n)$ then $\alpha \in \Oh(\log n)$ by strong duality + \end{center} \end{frame} \begin{frame} - \frametitle{Dual Program} + \frametitle{Solution of the dual} \begin{block}{Dual Program} + Let $\Ih$ be the exponenitally large set of \structure{all pathtrees}. \begin{alignat}{3} - \max_{\structure{\Ell, z}} \quad & \mathrlap{\structure{z}}\\ % + \max_{\structure{z, \Ell}} \quad & \mathrlap{\structure{z}}\\ % \st \quad && \sum_{u, v \in V} c_{uv} \structure{\ell_{uv}} &= 1 \\ - && \structure{z} & \leq \sum_{e_T \in T_i} C_i(e_T) \sum_{(u,v) \in P_i(e_T)} \structure{\ell_{uv}} & \quad \forall i \in \Ih \\ + \only<-2>{ + && \structure{z} & \leq \sum_{e_T \in T_i} C_i(e_T) \tikzmark{a}\sum_{(u,v) \in P_i(e_T)} \structure{\ell_{uv}} \tikzmark{b} & \qquad \forall i \in \Ih \\ + } + \only<3-4>{ + && \structure{z} & \leq \tikzmark{c}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)\tikzmark{d} & \qquad \forall i \in \Ih \\ + } + \only<5->{ + && \structure{z} & \leq \min_{i \in \Ih}\sum_{e_T \in T_i} C_i(e_T) d_{\structure{\ell}}(e_T)\\ + } && \structure{\Ell} &\geq 0 \end{alignat} \end{block} + + \vfill + + \begin{itemize} + \item We interpret the $\ell_{uv}$ as edge lengths in $G$ + \item They define a \structure{shortest path metric $d_{\structure{\ell}}(u, v)$} + \item For an edge $e = (x, y)$ we write $d_{\structure{\ell}}(e) \defeq d_{\structure{\ell}}(x, y)$ + \end{itemize} + \begin{tikzpicture}[remember picture, overlay] + \only<2> {% + \node[fit=(a)(b), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below:{$\geq d_{\structure{\ell}}(e_T)$}}] {}; + } + \only<4> {% + \node[fit=(c)(d), highlight, minimum height=3.5em, inner sep=-3pt, label={[tumorange, font=\small]below right:{$\geq \min_{i \in \Ih} \cdots$}}] {}; + } + \end{tikzpicture} \end{frame} \begin{frame} - \frametitle{Proof of $\Oh(\log n)$ness} + \frametitle{Solution of the dual} - \begin{itemize} - \item Distance Metric - \item Normalization - \item inequalities - \end{itemize} + \begin{block}{Dual Program} + Let $\Ih$ be the exponenitally large set of \structure{all pathtrees}. + \only<1-2>{% + \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} + \vspace{-1em} + } + \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}}}\\ + \st \quad & \structure{\Ell} \geq 0 + \end{alignat} + } + \end{block} + + \vfill + + \uncover<2-3>{ + \begin{itemize} + \item Now suppose + \begin{align} + \sum_{u, v \in V} c_{uv} \ell_{uv} = \beta > 0 + \end{align} + \item If we scale every length by $\frac{1}{\beta}$ our solution will change by $\frac{1}{\beta}$ + \end{itemize} + } + \begin{tikzpicture}[remember picture, overlay] + \only<2>{ + \node[fit=(a)(b), highlight, minimum height=2.5em, inner sep=-3pt] {}; + } + \end{tikzpicture} \end{frame} \begin{frame} @@ -522,6 +605,12 @@ \end{frame} \begin{frame} + \frametitle{Inequality Fun \#2} + + content +\end{frame} + +\begin{frame} \frametitle{Tree goodness} content diff -r f753b74f0e72 -r 1b2e38c66a67 minimum_bisection/tikzpictures.tex --- a/minimum_bisection/tikzpictures.tex Mon May 19 13:37:32 2014 +0200 +++ b/minimum_bisection/tikzpictures.tex Tue May 20 18:45:32 2014 +0200 @@ -17,6 +17,10 @@ \tikzstyle{flow capacity} = [node on edge] \tikzstyle{flow demand} = [node on edge, text=tumred] +\tikzstyle{highlight} = [draw=tumorange, very thick, rounded corners] + +\newcommand{\tikzmark}[1]{\tikz[overlay,remember picture,baseline] \node [anchor=base] (#1) {};} + \newcommand{\flownodes}{% \pgfmathsetseed{42} \def\jiggliness{0.2}