TY - JOUR

T1 - An Optimal Algorithm for the Weighted Backup 2-Center Problem on a Tree

AU - Wang, Hung Lung

N1 - 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 -