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.

# A Decomposition Theorem for Dynamic Flows

Lukas Graf, Julian Schwarz, Tobias Harks
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]}$
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$
$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

\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

• Characterization of edge-flows having a pure walk-decomposition
• Finite walk-decomposition if edge-traversal times are lower bounded

## Open Questionsmmmmmmmmmmmm

• Computational Complexity
• "Nice" Decompositions
• Existence of Path-Decomposition
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