The backup 2-center and backup 2-median problems on trees

In this paper, we are concerned with the problem of deploying two servers in a tree network, where each server may fail with a given probability. Once a server fails, the other server will take full responsibility for the services. Here, we assume that the servers do not fail simultaneously. In the...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2009-01, Vol.53 (1), p.39-49
Main Authors: Wang, Hung-Lung, Wu, Bang Ye, Chao, Kun-Mao
Format: Article
Language:English
Subjects:
Applied sciences
center
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Exact sciences and technology
location problem
Logistics
median
Operational research and scientific management
Operational research. Management science
Software
tree
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we are concerned with the problem of deploying two servers in a tree network, where each server may fail with a given probability. Once a server fails, the other server will take full responsibility for the services. Here, we assume that the servers do not fail simultaneously. In the backup 2‐center problem, we want to deploy two servers at the vertices such that the expected distance from a farthest vertex to the closest functioning server is minimum. In the backup 2‐median problem, we want to deploy two servers at the vertices such that the expected sum of distances from all vertices to the set of functioning servers is minimum. We propose an O(n)‐time algorithm for the backup 2‐center problem and an O(n log n)‐time algorithm for the backup 2‐median problem, where n is the number of vertices in the given tree network. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009
ISSN:0028-3045
1097-0037
DOI:10.1002/net.20261