Minsum $k$-Sink Problem on Path Networks

Abstract

We consider the problem of locating a set of $k$ sinks on a path network with general edge capacities that minimizes the sum of the evacuation times of all evacuees. We first present an $O(kn{\log }^{4}n)$ time algorithm when the edge capacities are non-uniform, where $n$ is the number of vertices. We then present an $O(kn{\log }^{3}n)$ time algorithm when the edge capacities are uniform. We also present an $O(n\log n)$ time algorithm for the special case where $k=1$ and the edge capacities are non-uniform.

22 pages, 4 figures