Almost linear time algorithms for minsum k-sink problems on dynamic flow path networks
Almost linear time algorithms for minsum k-sink problems on dynamic flow path networks
复制标题
动态流路网络上最小和 k 汇问题的几乎线性时间算法
DOI：
10.1016/j.tcs.2021.05.003
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Koji Watase
中科院分区：
文献类型：
--
作者：
Yuya Higashikawa;Naoki Katoh;Junichi Teruyama;Koji Watase
研究了动态流路网络上的设施选址问题。动态流路径网络由具有正边长、正边容量和正顶点权重的无向路径组成。路径可以被认为是一条道路，边的长度是沿着道路的距离，顶点的权重是站点上的人数。边缘容量限制了单位时间内可以进入边缘的人数。在动态流网络中，给定边或顶点上的特定点（称为汇点），所有的人都尽可能快地从顶点疏散到汇点。问题是以这样的方式在动态流路网络上找到汇的位置，即，所有人疏散到水池的时间的总和被最小化。我们考虑了两种模型：汇流模型和非汇流模型。在前一种模型中，对疏散方式进行了限制，使得在一个顶点上的所有人都必须疏散到同一个水槽，而在后一种模型中，没有这样的限制。在本文中，对于这两个模型，我们开发的算法，运行在几乎线性的时间，无论汇的数量。应该强调的是，对于合流流模型，我们的算法改进了Benkoczi等人[Theoretical Computer Science，2020]的先前结果，而对于非合流流模型，我们的算法是第一个多项式时间算法。
We address the facility location problems on dynamic flow path networks. Adynamic flow path networkconsists of an undirected path with positive edge lengths, positive edge capacities, and positive vertex weights. A path can be considered as a road, an edge length as the distance along the road and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. In the dynamic flow network, given particular points on edges or vertices, calledsinks, all the people evacuate from the vertices to the sinks as quickly as possible. The problem is to find the location of sinks on a dynamic flow path network in such a way that the aggregate evacuation time (i.e., the sum of evacuation times for all the people) to sinks is minimized. We consider two models of the problem: theconfluent flow modeland thenon-confluent flow model. In the former model, the way of evacuation is restricted so that all the people at a vertex have to evacuate to the same sink, and in the latter model, there is no such restriction. In this paper, for both the models, we develop algorithms which run in almost linear time regardless of the number of sinks. It should be stressed that for the confluent flow model, our algorithm improves upon the previous result by Benkoczi et al. [Theoretical Computer Science, 2020], and one for the non-confluent flow model is the first polynomial time algorithm.