论文标题
串联网络中动态平衡的计算
Computation of Dynamic Equilibria in Series-Parallel Networks
论文作者
论文摘要
在流体排队模型下，我们考虑了随时间流的动态平衡。在此模型中，网络链接的排队会照顾流的传播。流以单个来源进入网络，并在一个水槽处叶。在动态平衡中，考虑到其余流动的模式，每个无限的小流粒子都尽早到达水槽。尽管该模型已经检查了数十年，但进展却相对较新。特别是，动态平衡的衍生物已被表征为重置的薄流，从而获得了更多结构性结果。我们的两个主要结果是基于以线性互补性问题及其分析的重置薄流的制定。如果流入率是正确的 - 单酮，我们提供了动态平衡的建设性证明。计算薄流与重置的复杂性（作为此方法的子问题）仍然是开放的。我们通过提供递归算法来解决两端串联 - 平行网络的类别，该算法在多项式时间内同时解决所有流动值的问题。
We consider dynamic equilibria for flows over time under the fluid queuing model. In this model, queues on the links of a network take care of flow propagation. Flow enters the network at a single source and leaves at a single sink. In a dynamic equilibrium, every infinitesimally small flow particle reaches the sink as early as possible given the pattern of the rest of the flow. While this model has been examined for many decades, progress has been relatively recent. In particular, the derivatives of dynamic equilibria have been characterized as thin flows with resetting, which allowed for more structural results. Our two main results are based on the formulation of thin flows with resetting as linear complementarity problem and its analysis. We present a constructive proof of existence for dynamic equilibria if the inflow rate is right-monotone. The complexity of computing thin flows with resetting, which occurs as a subproblem in this method, is still open. We settle it for the class of two-terminal series-parallel networks by giving a recursive algorithm that solves the problem for all flow values simultaneously in polynomial time.
