Multiple sink location problem in path networks with a combinational objective
Document Type
Article
Publication Date
2021
Department/School
Computer Science
Publication Title
Optimization Letters
Abstract
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(n6) for general k, respectively.
Link to Published Version
Recommended Citation
Luo, T., Li, H., Ru, S., Tong, W., & Xu, Y. (2021). Multiple sink location problem in path networks with a combinational objective. Optimization Letters, 15(2), 733–755. https://doi.org/10.1007/s11590-020-01597-w