Multiple sink location problem in path networks with a combinational objective

In this paper, we consider the k-sink location problem in a path network with the goal of optimizing a combinational function of the maximum completion time and the total completion time. Let P= (V, E) be an undirected path network with n vertices. Each vertex has a positive weight, indicating the initial amount of supplies, and each edge has a positive length and a uniform capacity, which is the maximum amount of supplies that can enter the edge per unit time. Our goal is to identify k sink locations on the path P so that all supplies will be successfully evacuated and the given objective function is optimized. This paper presents two efficient polynomial time algorithms, which achieve O(n) for k= 1 and O(n⁶) for general k, respectively.