# HG changeset patch # User Markus Kaiser # Date 1400366964 -7200 # Node ID 2af28ac8a070c5b30d44c3393f0884d2bc6a5e55 # Parent e852e2a62ce4b569d01353a70c15f0bbbb5da702 first few slides diff -r e852e2a62ce4 -r 2af28ac8a070 minimum_bisection/preamble.tex --- a/minimum_bisection/preamble.tex Sat May 17 16:44:50 2014 +0200 +++ b/minimum_bisection/preamble.tex Sun May 18 00:49:24 2014 +0200 @@ -19,11 +19,8 @@ \usepackage{tikz} \usepackage{pgfplots} \pgfplotsset{compat=1.8} -\usetikzlibrary{automata} -\usetikzlibrary{calc} \usetikzlibrary{shapes} -\usetikzlibrary{positioning} -\usetikzlibrary{chains} +\usetikzlibrary{fit} \usepackage{amsmath} \usepackage{mathdots} @@ -44,6 +41,8 @@ \newcommand{\C}{\mathbb{C}} \newcommand{\Prob}{\mathrm{P}} \newcommand{\Oh}{\mathcal{O}} +\newcommand{\Ih}{\mathcal{I}} +\newcommand{\Ell}{\mathcal{L}} \newcommand{\abs}[1]{\left\vert #1 \right\vert} \newcommand{\powerset}[1]{\mathcal{P}\left( #1 \right)} @@ -52,13 +51,4 @@ \newcommand{\defeq}{\coloneqq} %Mathtools already defines this -\pgfdeclarelayer{background} -\pgfdeclarelayer{foreground} -\pgfsetlayers{background,main,foreground} - -\tikzstyle{edge} = [draw,very thick,->,>=latex] -\tikzstyle{pretty} = [circle,thick,draw,fill=tumblue!10] -\tikzstyle{every edge} = [edge] -\tikzstyle{every state} = [pretty] -\tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] -\tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\Huge] +\DeclareMathOperator{\st}{s.t.} diff -r e852e2a62ce4 -r 2af28ac8a070 minimum_bisection/presentation.tex --- a/minimum_bisection/presentation.tex Sat May 17 16:44:50 2014 +0200 +++ b/minimum_bisection/presentation.tex Sun May 18 00:49:24 2014 +0200 @@ -1,4 +1,5 @@ \input{preamble.tex} +\input{tikzpictures.tex} \title{Oblivious Routing and Minimum Bisection} \subtitle{Approximation Algorithms Seminar} @@ -10,4 +11,221 @@ \titlepage \end{frame} +\begin{frame} + \frametitle{Flow Problems} + \begin{problem}[Single Commodity Flow] + Given + \begin{itemize}[<+->] + \item An (un)directed Graph $G = (V, E)$ + \item A \structure{capacity function} $c : E \to \R^+$ + \item A source $s$ and a target $t$ + \end{itemize} + \uncover<4->{Calculate the maximum possible \structure{flow} $f : E \to \R^+$ through $G$.} + \end{problem} + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges[directed] + \only<2->{\flowcapacities} + + \draw<3-> + (n.south) node[below] {\structure{s}} + (j.south) node[below] {\structure{t}}; + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Flow Problems} + + \begin{problem}[Multi Commodity Flow] + Given + \begin{itemize} + \item An undirected Graph $G = (V, E)$ + \item A capacity function $c : E \to \R^+$ + \item<2-> A \structure{demand function} $d : V^2 \to \R^+$ + \end{itemize} + \uncover<3->{Calculate the flow $f$ with least \structure{congestion $\rho = \max_{e \in E}\frac{f_e}{c_e}$}.} + \end{problem} + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowcapacities + \only<2->{\flowdemands} + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Oblivious Routing} + + \begin{problem}[Oblivious Routing] + Given + \begin{itemize} + \item An undirected Graph $G = (V, E)$ + \item A capacity function $c : E \to \R^+$ + \end{itemize} + Calculate a combination of paths for each $(u, v) \in V^2$ such that for \alert{any} demand function the \structure{congestion} will be as small as possible. + \end{problem} + + \centering + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowcapacities + + \draw<2-> + (n.south) node[below] {\structure{u}} + (j.south) node[below] {\structure{v}}; + + \only<3-> { + \begin{pgfonlayer}{marked} + \draw[marked edge, tumgreen] + (n.center) edge (l.center) + (l.center) edge (h.center) + (h.center) edge (i.center) + (i.center) edge (j.center); + + \draw[marked edge, tumblue] + (n.center) edge (m.center) + (m.center) edge (e.center) + (e.center) edge (c.center) + (c.center) edge (k.center) + (k.center) edge (j.center); + + \draw[marked edge, tumred] + (n.center) edge (b.center) + (b.center) edge (j.center); + \end{pgfonlayer} + + \path[font=\Large] + (n) + +(-0.5, 0.5) node[tumgreen] {$\frac{1}{4}$} + +(-0.5, 0) node[tumblue] {$\frac{1}{2}$} + +(-0.5, -0.5) node[tumred] {$\frac{1}{4}$}; + } + \end{tikzpicture} +\end{frame} + +\begin{frame} + \frametitle{Oblivious Routing} + + \begin{center} + \begin{tikzpicture}[flow graph] + \flownodes + \flowedges + \flowtreeedges + \flowcapacities + \flowdemands + + \begin{pgfonlayer}{background} + \node[draw=tumblue, fill=tumblue!20, thick, ellipse, rotate fit=30, fit=(g)(i)(k)(j), inner sep=3pt] {}; + \end{pgfonlayer} + \end{tikzpicture} + \end{center} +\end{frame} + +\begin{frame} + \frametitle{Definitions} + + \begin{itemize} + \item Graph + \item Spanning Tree + \item Cut + \item Demand + \item Congestion + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Routing with a Tree} + + content +\end{frame} + +\begin{frame} + \frametitle{Routing with convex Combinations} + + content +\end{frame} + +\begin{frame} + \frametitle{Routing with convex Combinations and Pathtrees} + + content +\end{frame} + +\begin{frame} + \frametitle{Primal Program} + + \begin{block}{Primal Program} + \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 \\ + && \structure{\lambda} &\geq 0 + \end{alignat} + \end{block} +\end{frame} + +\begin{frame} + \frametitle{Dual Program} + + \begin{block}{Dual Program} + \begin{alignat}{3} + \max_{\structure{\Ell, z}} \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 \\ + && \structure{\Ell} &\geq 0 + \end{alignat} + \end{block} +\end{frame} + +\begin{frame} + \frametitle{Proof of $\Oh(\log n)$ness} + + \begin{itemize} + \item Distance Metric + \item Normalization + \item inequalities + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Polynomial Algorithm} + + content +\end{frame} + +\begin{frame} + \frametitle{Minimum Bisection Problem} + + content +\end{frame} + +\begin{frame} + \frametitle{Solution Algorithm} + + content +\end{frame} + +\begin{frame} + \frametitle{Inequality Fun \#2} + + content +\end{frame} + +\begin{frame} + \frametitle{Tree goodness} + + content +\end{frame} + +\begin{frame} + \frametitle{Solution of MB on trees} + + content +\end{frame} + \end{document} diff -r e852e2a62ce4 -r 2af28ac8a070 minimum_bisection/tikzpictures.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/minimum_bisection/tikzpictures.tex Sun May 18 00:49:24 2014 +0200 @@ -0,0 +1,88 @@ +\pgfdeclarelayer{background} +\pgfdeclarelayer{demand} +\pgfdeclarelayer{marked} +\pgfdeclarelayer{foreground} +\pgfsetlayers{background,demand,marked,main,foreground} + +\tikzstyle{edge} = [thick] +\tikzstyle{marked edge} = [edge, line width=3pt, tumorange] +\tikzstyle{directed} = [arrows={-latex}, shorten >=1pt] +\tikzstyle{node on edge} = [fill=white, circle, inner sep=1pt, font=\footnotesize] + +\tikzstyle{flow graph} = [x=4em, y=5em] +\tikzstyle{flow node} = [circle, draw, thick, fill=tumblue!20, minimum size=6pt, inner sep=0pt] +\tikzstyle{flow edge} = [edge] +\tikzstyle{demand edge} = [edge, line width=2.5pt, arrows={-latex}, dotted, tumred!50] +\tikzstyle{tree edge} = [marked edge, tumgreen] +\tikzstyle{flow capacity} = [node on edge] +\tikzstyle{flow demand} = [node on edge, text=tumred] + +\newcommand{\flownodes}{% + \pgfmathsetseed{42} + \def\jiggliness{0.2} + \def\jiggle{++ (random * \jiggliness, random * \jiggliness)} + + \path[use as bounding box] (-4, 2.7) rectangle (3.5,6.15); + + \foreach \pos/\name in { + % {(0,1)/a}, + {(-0.5,2.75)/b}, + {(0.5,3.25)/c}, + {(0.75,4)/d}, + {(-0.5,4.5)/e}, + {(-1.25,3.75)/f}, + {(1.5,4.75)/g}, + {(0,5.5)/h}, + {(2.5,5.5)/i}, + {(3.5,3.5)/j}, + {(2.25,4)/k}, + {(-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) {}; +} +\newcommand{\flowedges}[1][]{% + \foreach \source/\dest in { + % {a/b}, {a/n}, {a/j}, + {n/b}, {b/j}, {f/b}, {c/b}, + {c/d}, {e/d}, {e/f}, {g/i}, + {h/e}, {h/i}, {i/j}, {k/j}, + {l/h}, {l/m}, {n/m}, + {c/k}, {k/i}, {g/d}, {m/e}, {n/l}, + {m/f}, {f/c}, {d/k}, {e/g}, {c/e}} + \draw[flow edge, #1] (\source) edge (\dest); +} +\newcommand{\flowcapacities}[1][]{% + \foreach \source/\dest/\capacity in { + % {a/b}, {a/n}, {a/j}, + {n/b/2}, {b/j/10}, {c/b/3}, {f/b/4}, + {c/d/1}, {e/d/2}, {e/f/4}, {g/i/2}, + {h/e/1}, {h/i/2}, {i/j/6}, {k/j/4}, + {l/h/3}, {l/m/3}, {n/m/5}, + {c/k/4}, {k/i/3}, {g/d/1}, {m/e/4}, {n/l/6}, + {m/f/1}, {f/c/2}, {d/k/4}, {e/g/1}, {c/e/5}} + \path (\source) -- node[flow capacity, #1]{\capacity} (\dest); +} +\newcommand{\flowdemands}{% + \begin{pgfonlayer}{demand} + \foreach \source/\dest/\demand/\pos/\bendage in { + {n/j/10/0.2/right}, + {h/j/8/0.2/left}, + {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) edge node[flow demand, pos=\pos]{\demand} (\dest); + \end{pgfonlayer} +} +\newcommand{\flowtreeedges}[1][]{% + \begin{pgfonlayer}{marked} + \foreach \source/ \dest in { + % {a/b}, + {c/b}, + {c/d}, {e/d}, {e/f}, {g/i}, + {h/e}, {h/i}, {i/j}, {k/j}, + {l/h}, {l/m}, {n/m}} + \draw[tree edge, #1] (\source.center) edge (\dest.center); + \end{pgfonlayer} +}