The Quickest Transshipment Problem is to route flow as quickly as possible from sources with supplies to sinks with demands in a network with capacities and transit times on the arcs. It is of fundamental importance for numerous applications in areas such as logistics, production, traffic, evacuation, and finance. More than 25 years ago, Hoppe and Tardos presented the first (strongly) polynomial-time algorithm for this problem. Their approach, as well as subsequently derived algorithms with strongly polynomial running time, are hardly practical as they rely on parametric submodular function minimization via Megiddo's method of parametric search. The main contribution of this paper is a considerably faster algorithm for the Quickest Transshipment Problem that instead employs a subtle extension of the Discrete Newton Method. This improves the previously best known running time of $\tilde{O}(m^4k^{14})$ to $\tilde O(m^2k^5+m^3k^3+m^3n)$, where $n$ is the number of nodes, $m$ the number of arcs, and $k$ the number of sources and sinks.
翻译：快速转口问题是,如何尽快从具有补给源的源头到在电弧上具有容量和中转时间的网络中的需求的汇中汇流流,这对物流、生产、交通、疏散和金融等领域的众多应用至关重要。25多年前,霍普和塔多斯提出了这一问题的第一个(强烈的)多时算法。他们的方法以及随后得到的具有强烈多元运行时间的参数算法几乎不切实际,因为他们依赖通过Megiddo的参数搜索方法将参数亚模函数最小化。本文的主要贡献是对快速转口问题的快速算法,而不是对分散式牛顿方法进行微妙的扩展。这改善了以前已知的最佳运行时间$tilde{O}(m4k ⁇ 14})到$\tilde O(m2k}5+m3k}3+m}3cmm}3nnn,因为它们依赖通过Megiddo的参数搜索方法将参数的亚模函数最小化为最小化。本文的主要贡献是对快速转口问题的快速算法,而采用快速的算法,而不是对分散式Newrete Newton Newton Newton 方法的扩展方法的扩展方法。这改进了以前已知的运行时间将美元和汇数和汇码数。
相关内容
微信扫码咨询专知VIP会员