Locating a broadcast facility in an unreliable network

A simple model of an unreliable communications network is a probabilistic graph in which each edge has some independent probability of being operational. The Network Broadcast Faciltiy location problem is to identify a node for which the expected number of nodes connected to it in the presence of random edge failures is as large as possible. This problem is, in fact, a special case of the stochastic 1-median problem. In this paper both problems are shown to be NP-hard. In light of this apparent intractibility, a location strategy based on efficiently computable two-terminal reliability bounds is suggested. This location strategy does not guarantee to find the best location but instead limits the choice to a subset of the nodes which contain the most resilient nodes of the network. The success of this approach depends on obtaining sufficiently tight reliability bounds. Edge-packing methods for computing upper and lower two-terminal bounds, as well as global methods for tightening these bounds are discussed. The authors illustrate the location strategy using an example network with 59 nodes and 71 edges. They conclude from this example that the location strategy shows promise as a filtering scheme for screening potential locations.