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 wj associated with every vertex uj. It is assumed that every edge (ui,uj) has a probability of failure pij 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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 47 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.