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 -