.png){kind=icon}
返回
Time-Dependent Minimum Cost Dynamic Flow Problems
.png){kind=icon}
PRE
AI
DOI：10.1007/s40305-025-00620-0.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
在本论文中，我们研究离散时间模型下动态网络中的最小费用流问题，该问题已知为NP难问题。该网络中的所有属性，包括容量、存储容量、费用、存储费用以及任意节点的供需量，均与时间相关。首先，我们证明可行动态流的存在性与求解时间相关的最大动态流问题等价，并为此可行性问题提供一个计算复杂度为$\mathcal{O}((m+n)n^2T^3)$的伪多项式时间精确算法，其中$m$和$n$分别为网络中的弧数和节点数，$T$为给定的时间跨度。接下来，基于可行动态流，我们提出一种扩展的费用缩放算法，可在$\mathcal{O}((m+n)n^2T^3\log(nCT))$时间内正确计算出时间相关的最小费用动态流，其中$C$表示网络中所有费用的最大绝对值。
Keyword:
Time-dependent
Minimum cost dynamic flow
Maximum dynamic flow
Pseudopolynomial-time algorithm
Cost scaling
期刊
J
IF:
1.1
论文数:
72
被引数:
487
机构
暂无机构信息
.png){kind=icon}
查看更多内容