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.