Skip to content
Preprint

Generalized Flows over Time: Complexity, Structure and Algorithm

Nov 2026 · 0 citations · 31 references
Computer Science

TL;DR

It is proved that the generalized maximum flow over time problem remains NP-hard under standard binary encoding, even on lossy two-terminal series-parallel networks, and it is proved that an optimal solution always exists without intermediate storage.

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.

View source

Similar papers

Preprint Nov 2026

Optimizing the Steady-State Travel Time of Nash Flows over Time with Capacity Increases

We study budgeted capacity augmentation for single-source single-sink \NFOTs under constant inflow $u_0$. The goal is to increase capacities on arcs subject to a global budget constraint in order to minimize the steady-state travel time in the network. We show that this problem is weakly NP-hard on series-parallel netw...

Niklas Dahlmeier, Paul Paschmanns, Laura Ritter et al. · 0 citations
Preprint Oct 2026

Constant-Factor Approximation for Non-Splitting Coflow Scheduling in Heterogeneous Parallel Networks via Iterative Relaxation

Coflows capture the collective communication requirements of data-parallel applications, and scheduling them well is essential to the performance of modern data centers. We study non-splitting coflow scheduling in a heterogeneous parallel network whose $m$ network cores may be Electronic Packet Switches (EPS), not-all-...

Chi-Yeh Chen · 0 citations
Preprint Oct 2026

An Efficient Algorithm for the Quickest Path Reliability Problem

This paper proposes an exact algorithm that generates the corresponding lower boundary state vectors without first enumerating minimal paths, and generates the exact complete set of lower bounds without any duplicates.

M. Forghani-elahabad · 0 citations
Preprint Oct 2026

Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks

Network coding lets the nodes of a network combine messages rather than merely forward them. In undirected networks, where the two directions of an edge share its capacity, Li and Li conjectured in 2004 that coding offers no advantage over fractional routing; the conjecture has been confirmed for many special classes b...

Xin-Dan Zhang, Bao-Chun Li, Zong-Peng Li · 5 citations
Preprint Oct 2026

Pipelining vs. Combining in Aggregation Tasks

We study the aggregation task (convergecast) in networks in the case that the values to be aggregated do not fit in a single message. We assume that every node starts with an input value, and there is an aggregation operator that is commutative, associative, and length-preserving, i.e., the result of aggregating two va...

Gabriel Marques Domingues, C. Mathieu, B. Patt-Shamir · 0 citations
Nov 2026

Scalable Capacity‐Constrained Power Diagrams via Compressed Optimal Assignment

Power diagrams with prescribed capacities are widely used in geometry processing, including blue‐noise sampling, remeshing, and constrained clustering. The problem can be viewed as a semi‐discrete optimal transport problem and is commonly discretized by dense sampling into a capacity‐constrained assignment between...

Jian-Tao Song, Yun-Qi Yang, Shuang-Min Chen et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.