Location of facilities on a network subject to a single‐edge failure

Abstract

Abstract In this work, the following location problem is analyzed. Let N = (V,E) be an undirected connected simple network, where V is the vertex set, | V | = n and E is the edge set. There is a nonnegative demand w j associated with every vertex u j . It is assumed that every edge (u i ,u j ) has a probability of failure p ij and that failures can never occur on two edges simultaneously. The problem consists of locating p facilities on the network so that the total expected demand disconnected from the facilities is minimized. This problem occurs naturally in the fields of computer and telecommunications networks. A number of important results are proved. First, there always exists a solution in which all facilities are located at vertices. Second, the problem can always be solved optimally on the so‐called leaf‐tree associated with the network. Third, when p = 1, the problem is a 1‐median problem. When p > 1, there always exists an optimal solution for which all facilities are located at pendent vertices of the tree. Finally, when p > 2, the problem with p + 1 facilities can be solved in a greedy fashion, starting from a solution to the problem with p facilities. An exact algorithm for this problem is described. It can be executed in either O ( np + | E |) time or in O ( n log n + | E |) time. A numerical example is provided.