Minsum k-Sink Problem on Dynamic Flow Path Networks

In emergencies such as earthquakes, nuclear accidents, etc., we need an evacuation plan. We model a street, a building corridor, etc. by a path network, and consider the problem of locating a set of k sinks on a dynamic flow path network with n vertices, where people are located, that minimizes the sum of the evacuation times of all evacuees. Our minsum model is more difficult to deal with than the minmax model, because the cost function is not monotone along the path. We present an \(O(kn^2\log ^2 n)\) time algorithm for solving this problem, which is the first polynomial time result. If the edge capacities are uniform, we give an \(O(kn\log ^3 n)\) time algorithm.