Metraipolis › archive › dc_44090f3fb775
Generalized Flows over Time: Complexity, Structure and Algorithm — arXiv:2611.02481
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.02481
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:58:59.970Z
- SHA-256 of the archived text
3e409c5b6c4ad2563ef63814f590923367e5826398f0405b919b1f52b63d2fca- Stable URL of this page
https://metraipolis.com/documento/dc_44090f3fb775
How to cite
Generalized Flows over Time: Complexity, Structure and Algorithm — arXiv:2611.02481 — arXiv (en), https://arxiv.org/abs/2611.02481 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_44090f3fb775 (Metraipolis archive dc_44090f3fb775, sha256 3e409c5b6c4ad2563ef63814f590923367e5826398f0405b919b1f52b63d2fca)
BibTeX
@misc{dc44090f3fb775,
title = {Generalized Flows over Time: Complexity, Structure and Algorithm — arXiv:2611.02481},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.02481},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_44090f3fb775; sha256 3e409c5b6c4ad2563ef63814f590923367e5826398f0405b919b1f52b63d2fca},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02481. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2611.02481 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T18:18:07.735Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).