Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

\( \newcommand{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRsp}{\IR_{\gt 0}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\mathbb{C}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\U}{\mathfrak{U}} \newcommand{\coloneqq}{:=} \newcommand{\Set}[1]{\left\{#1\right\}} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\Mid}{\,\middle|\,} \newcommand{\supp}{\mathrm{supp}} \newcommand{\Re}{\mathrm{Re}} \newcommand{\Im}{\mathrm{Im}} \newcommand{\clos}[1]{\overline{#1}} \newcommand{\inte}[1]{\mathring{#1}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{{\Large\raise{0pt}{\unicode{x1D7D9}}\,}} \newcommand{\Indn}{{\raise{-1pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\scalar}[2]{\left\langle #1,#2 \right\rangle} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\queue}{q} \newcommand{\Pc}{\mathcal{P}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Wc}{\mathcal{W}} \newcommand{\diff}{\mathrm{d}} \newcommand{\eps}{\varepsilon} \newcommand{\ql}[1][e]{Q_{#1}} \newcommand{\hori}{[0,T]} \)

A Decomposition Theorem for Dynamic Flows

Lukas Graf, Julian Schwarz, Tobias Harks
→ PDF-Version (static)    
Dagstuhl Seminar
$y_{p_3}=4$
$y_{p_4}=2$
$y_{p_2}=3$
$y_{p_1}\,$$=2$
$y_{p_2}\,$$=5$
$y_{p_3}\,$$=2$
$y_{p_4}\,$$=0$
$h_{p_1}=4\cdot\Ind_{[0,7]}$
$h_{p_4}=3\cdot\Ind_{[0,5]}$
4 2 2 4{\scriptsize\Indn}_{[2,4]}+7{\scriptsize\Indn}_{[4,9]} 5 9 4 2 7 2 4 2 2 s d
path flow
$(y_p) \in \IRnn^{\Pc}$
path/cycle flow
$(y_p) \in \IRnn^{\Pc\cup\Cc}$
path inflow
$(h_p) \in L_+(\hori)^{\Pc}$
walk/cycle inflow
$(h_p) \in L_+(\hori)^{\Wc\cup\Cc}$
edge flow
$(x_e) \in \IRnn^{E}$
edge $s$,$d$-flow
$(x_e) \in \IRnn^{E}$
(satisfying flow cons.)
$u$-based edge flow
$(g_e) \in L_+(\hori)^{E}$

w.r.t. traversal times
$D_e(g,.): \IR \to \IRnn$

arrival times
$A_p(g,.): \IR \to \IRnn$

w.r.t. traversal times
$D_e({\color{red}u},.): \IR \to \IRnn$

arrival times
$A_p({\color{red}u},.): \IR \to \IRnn$

w.r.t. traversal times
$D_e(u,.): \IR \to \IRnn$

arrival times
$A_p(u,.): \IR \to \IRnn$
$\sum_{p \ni e}y_p = x_e$
$\sum_{p \ni e}h_p(\_ - \tau_{p|_{\lt e}}) = g_e$
$\sum_{p\,,j:p[j]\,=e}\int_{A_{p\,,j}(g,.)^{-1}([0,t])}h_p\,(\theta)\diff\theta = \int_0^t {g}_e(\theta)\diff\theta$
$\sum_{p\,,j:p[j]\,=e}\int_{A_{p\,,j}({\color{red}g},.)^{-1}([0,t])}h_p\,(\theta)\diff\theta = \int_0^t {\color{red}g}_e(\theta)\diff\theta$
$\sum_{w,j:w[j]=e}\int_{A_{w,j}({g},.)^{-1}([0,t])}h_w(\theta)\diff\theta = \int_0^t {g}_e(\theta)\diff\theta$
$\sum_{w,j:w[j]=e}\int_{A_{w,j}({\color{red}u},.)^{-1}([0,t])}h_w(\theta)\diff\theta = \int_0^t {g}_e(\theta)\diff\theta$
$\sum_{w,j:w[j]=e}\int_{A_{w,j}({u},.)^{-1}([0,t])}h_w(\theta)\diff\theta = \int_0^t {g}_e(\theta)\diff\theta$
network-loading
$u$-based network-loading $\ell^u$
(c.f. e.g. [ZM00], [HFY13], [CCL15], [XWFMZ99], [Koc12], ...)
flow-decomposition
$u$-based flow-decomposition
Input: edge based $s$,$d$-flow $(x_e)$
Output: path-decomposition $(y_p)$ s.th. "$x-y$" is circulation
(1) Fix some order on $\Pc = \Set{p_1, \dots, p_K}$
(2) For $k = 1, \dots, K$ Do
(3) .. Remove maximal amount of flow $y_{p_k}$ on $p_k$ from $x$
Input: edge based $s$,$d$-flow $(g_e)$
Output: walk-decomposition $(h_w)$ s.th. "$g-h$" is circulation
(1) Fix some order on $\Wc = \Set{w_1, w_2, \dots}$
(2) For $k = 1, 2, \dots$ Do
(3) .. Remove maximal amount of flow $h_{w_k}$ on $w_k$ from $g$
  • Definition & Existence of "maximal flow on $w_k$"
  • Correctness (Invariant and Consequences)
The above algorithm is correct / Every dynamic ($u$-based) $s$,$d$-flow has a walk-cycle decomposition.

Definition & Existence of Maximal Walk-Inflow

N A_{w,j}(u,.)^{-1}(N)
\begin{align} \max &&\quad\quad\!\!\!\!\phantom{\int_0^T}\vartheta(h) \tag{P}\\ \text{s.t. } &&\ell^u(h) &\leq g \notag\\ &&h &\in \mathcal{M} \notag \end{align}
\begin{align*} \max &&\int_0^T h_w(\theta)\diff\theta \\ \text{s.t. } &&\ell^u(h) &\leq g \\ &&h_w &\in \mathcal{D}_w \end{align*}
The domain $\mathcal{D}$ of $\ell^u$ is weakly closed.
Use:mmmm $\ell^u(h)$ exists $\iff h_w = 0$ on $A_{w,j}(u,.)^{-1}(N)$ for any null set $N$ and all $w, j$
$\vartheta$ weakly continuous, $\mathcal{M} \subseteq \mathcal{D}$ non-empty, weakly closed $\implies$ (P) has optimal solution.

Correctness

$u$-based $s$,$d$-flow $g$ $\implies$ $g-\ell^u(h_w)$ a $u$-based $s$,$d$-flow. mmmm(Invariant)
Any $u$-based $s$,$d$-flow satisfies
  1. Either: There exists a flow carrying $s$,$d$-walk mmmm(if source has net-outflow)
  2. Or: The flow is a dynamic circulation mmmmmmmi(if source has no net-outflow)

Further resultsmmmmmmmmmmmm

Open Questionsmmmmmmmmmmmm

A Decomposition Theorem for Dynamic Flows Lukas Graf
A Decomposition Theorem for Dynamic Flows - Problem Statement Lukas Graf
A Decomposition Theorem for Dynamic Flows - Algorithm: Well-definedness & Correctness Lukas Graf
A Decomposition Theorem for Dynamic Flows - Conclusion Lukas Graf