Description:
<jats:title>Abstract</jats:title><jats:p>In this work, the following location problem is analyzed. Let <jats:italic>N</jats:italic> = <jats:italic>(V,E)</jats:italic> be an undirected connected simple network, where <jats:italic>V</jats:italic> is the vertex set, |<jats:italic>V</jats:italic>| = <jats:italic>n</jats:italic> and <jats:italic>E</jats:italic> is the edge set. There is a nonnegative demand <jats:italic>w</jats:italic><jats:sub><jats:italic>j</jats:italic></jats:sub> associated with every vertex <jats:italic>u</jats:italic><jats:sub><jats:italic>j</jats:italic></jats:sub>. It is assumed that every edge <jats:italic>(u<jats:sub>i</jats:sub>,u<jats:sub>j</jats:sub>)</jats:italic> has a probability of failure <jats:italic>p</jats:italic><jats:sub><jats:italic>ij</jats:italic></jats:sub> and that failures can never occur on two edges simultaneously. The problem consists of locating <jats:italic>p</jats:italic> 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 <jats:italic>p</jats:italic> = 1, the problem is a 1‐median problem. When <jats:italic>p</jats:italic> > 1, there always exists an optimal solution for which all facilities are located at pendent vertices of the tree. Finally, when <jats:italic>p</jats:italic> > 2, the problem with <jats:italic>p</jats:italic> + 1 facilities can be solved in a greedy fashion, starting from a solution to the problem with <jats:italic>p</jats:italic> facilities. An exact algorithm for this problem is described. It can be executed in either <jats:italic>O</jats:italic>(<jats:italic>np</jats:italic> + |<jats:italic>E</jats:italic>|) time or in <jats:italic>O</jats:italic>(<jats:italic>n</jats:italic> log <jats:italic>n</jats:italic> + |<jats:italic>E</jats:italic>|) time. A numerical example is provided.</jats:p>