论文标题
Minsum $ K $ -SINK问题的几乎线性时间算法在动态流道网络上问题
Almost Linear Time Algorithms for Minsum $k$-Sink Problems on Dynamic Flow Path Networks
论文作者
论文摘要
我们解决了动态流道网络上的设施位置问题。动态流路径网络由一个无向路径组成，具有正边长度，正边能力和正顶点重量。可以将路径视为道路，边缘长度作为沿路的距离，而顶点的重量为现场人数。边缘容量限制了每单位时间可以进入边缘的人数。在动态流网络中，给定边缘或顶点上的特定点，称为水槽，所有人都会尽快从顶点撤离到水槽。问题是要以一种方式，以使总撤离时间（即所有人的撤离时间之和）以最小化的方式找到水槽的位置。我们考虑了两个问题的模型：汇合流模型和非集合流量模型。在以前的模型中，疏散方式受到限制，因此顶点的所有人都必须撤离到同一水槽，而在后一种模型中，没有这种限制。在本文中，对于这两个模型，我们都会开发出在几乎线性时间内运行的算法，而不论水槽的数量多少。应该强调的是，对于汇合流模型，我们的算法会根据Benkoczi等人的先前结果改善。 [理论计算机科学，2020年]，而对于非引发流动模型的一个是第一个多项式时间算法。
We address the facility location problems on dynamic flow path networks. A dynamic flow path network consists 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, called sinks, 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: the confluent flow model and the non-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.
