TY - JOUR
T1 - An Optimal Algorithm for the Weighted Backup 2-Center Problem on a Tree
AU - Wang, Hung Lung
N1 - Funding Information:
The author would like to thank the anonymous reviewer, whose helpful comments improve the readability. The author would also like to thank Professor Kun-Mao Chao, Ming-Wei Shao, and Jhih-Heng Huang for fruitful discussions. Hung-Lung Wang was supported in part by MOST Grant 103-2221-E-141-004, from the Ministry of Science and Technology, Taiwan.
Publisher Copyright:
© 2015, Springer Science+Business Media New York.
PY - 2017/2/1
Y1 - 2017/2/1
N2 - In this paper, we are concerned with the weighted backup 2-center problem on a tree. The backup 2-center problem is a kind of center facility location problem, in which one is asked to deploy two facilities, with a given probability to fail, in a network. Given that the two facilities do not fail simultaneously, the goal is to find two locations, possibly on edges, that minimize the expected value of the maximum distance over all vertices to their closest functioning facility. In the weighted setting, each vertex in the network is associated with a nonnegative weight, and the distance from vertex u to v is weighted by the weight of u. With the strategy of prune-and-search, we propose a linear time algorithm, which is asymptotically optimal, to solve the weighted backup 2-center problem on a tree.
AB - In this paper, we are concerned with the weighted backup 2-center problem on a tree. The backup 2-center problem is a kind of center facility location problem, in which one is asked to deploy two facilities, with a given probability to fail, in a network. Given that the two facilities do not fail simultaneously, the goal is to find two locations, possibly on edges, that minimize the expected value of the maximum distance over all vertices to their closest functioning facility. In the weighted setting, each vertex in the network is associated with a nonnegative weight, and the distance from vertex u to v is weighted by the weight of u. With the strategy of prune-and-search, we propose a linear time algorithm, which is asymptotically optimal, to solve the weighted backup 2-center problem on a tree.
KW - Backup 2-center
KW - Prune-and-search
KW - Quasiconvex function
KW - Weighted center
UR - http://www.scopus.com/inward/record.url?scp=84944593785&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84944593785&partnerID=8YFLogxK
U2 - 10.1007/s00453-015-0081-z
DO - 10.1007/s00453-015-0081-z
M3 - Article
AN - SCOPUS:84944593785
SN - 0178-4617
VL - 77
SP - 426
EP - 439
JO - Algorithmica
JF - Algorithmica
IS - 2
ER -