On the Delay-Constrained Maximum Concurrent Flow Problem
Abstract
Real-time services, such as VoIP and large-scale neural network training, require strict transmission delay guarantees. While routing under hop constraints is tractable, real-world delays increase sharply with equipment load, typically modeled using the M/M/1 queuing function where delay is inversely proportional to available bandwidth. We investigate the resulting Delay-Constrained Maximum Concurrent Flow (DCMCF) problem, which seeks to maximize the minimum throughput across all commodities. The problem's complexity stems from the conditional and non-linear nature of the delay constraints, which are active only along the specific paths used by the flow. We prove that DCMCF is strongly NP-hard, even for single-source/single-destination instances. To address the inherent non-convexity of the problem, we introduce a new convex relaxation expressed through second-order cone constraints, obtained from the convex envelope of a function representing the conditional delay associated with a single arc of a given path. The relaxation is shown to outperform existing formulations based on disjunctive programming. Leveraging this result, we develop a polynomial-time approximation algorithm with a provable performance guarantee and present numerical experiments demonstrating the effectiveness of the proposed approach.
Related
- Online Multi-Level Aggregation with Maximum Delay
- Distribution-constrained maximum stopping of maximum type
- A Spatial Benders Algorithm for Delay Constrained Routing
- Dynamic Optimistic Constrained OCO with Memory via Delay Equivalence
- Pontryagin maximum principle for non-smooth state-constrained control problems over Wasserstein spaces
BibTeX
@misc{benameur2026delayconstrained,
title = {{On the Delay-Constrained Maximum Concurrent Flow Problem}},
author = {Walid Ben-Ameur and Guillaume Beraud-Sudreau and Hervé Kerivin and Sebastien Martin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05068},
eprint = {2609.05068},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05068},
}
RIS
TY - UNPB
TI - On the Delay-Constrained Maximum Concurrent Flow Problem
AU - Walid Ben-Ameur
AU - Guillaume Beraud-Sudreau
AU - Hervé Kerivin
AU - Sebastien Martin
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05068
UR - https://arxiv.org/abs/2609.05068
AB - Real-time services, such as VoIP and large-scale neural network training, require strict transmission delay guarantees. While routing under hop constraints is tractable, real-world delays increase sharply with equipment load, typically modeled using the M/M/1 queuing function where delay is inversely proportional to available bandwidth. We investigate the resulting Delay-Constrained Maximum Concurrent Flow (DCMCF) problem, which seeks to maximize the minimum throughput across all commodities. The problem's complexity stems from the conditional and non-linear nature of the delay constraints, which are active only along the specific paths used by the flow. We prove that DCMCF is strongly NP-hard, even for single-source/single-destination instances. To address the inherent non-convexity of the problem, we introduce a new convex relaxation expressed through second-order cone constraints, obtained from the convex envelope of a function representing the conditional delay associated with a single arc of a given path. The relaxation is shown to outperform existing formulations based on disjunctive programming. Leveraging this result, we develop a polynomial-time approximation algorithm with a provable performance guarantee and present numerical experiments demonstrating the effectiveness of the proposed approach.
ER -