Generalized flows over time remain hard but enable new approximation methods
Generalized Flows over Time: Complexity, Structure and Algorithm
Data Structures and Algorithms
Summary
The paper studies complex network flows where things move with delays and can lose or gain quantity on the way. The authors show this problem is computationally hard even in simple networks, meaning no quick solution is likely. However, they find structural tricks that let you get close to the best answer efficiently. These tricks also work to minimize how much starts flowing to meet a demand by a deadline without needing to store flow midway.
What this means in practice
- •For network schedulers: Use approximation methods to plan flows with delays and losses efficiently, where exact scheduling is computationally infeasible.
- •For logistics planners: Determine minimum starting supplies needed to meet shipping demands on networks with transit delays and losses, without requiring intermediate storage.
A theory result. No direct application yet.
Authors
Siyuan Chen, Shengminjie Chen, Suixiang Gao, Zheyu Jiang, Dun Ma, Wenguo Yang
Abstract
Generalized flows over time constitute a general network flow model that incorporates both transit times and flow losses or gains. We study their complexity, structure, and approximation. We prove that the generalized maximum flow over time problem remains NP-hard under standard binary encoding, even on lossy two-terminal series-parallel networks. The maximum temporally repeated restriction is APX-hard with general gains and NP-hard on lossy networks. We then consider the minimum source supply needed to satisfy a fixed sink demand within a given horizon, and prove that an optimal solution always exists without intermediate storage. On lossy networks, such a solution can additionally use only simple source--sink paths. These structural properties yield a fully polynomial-time approximation scheme via time condensation, with analogous schemes for generalized maximum flows over time and quickest flows with a source-supply budget.