LOCATION OF FACILITIES ON A NETWORK SUBJECT TO A SINGLE-EDGE FAILURE

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 v(j). It is assumed that every edge (v(i),v(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.