The Approximability of Multiple Facility Location on Directed Networks with Random Arc Failures
- PDF / 3,240,897 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 3 Downloads / 150 Views
The Approximability of Multiple Facility Location on Directed Networks with Random Arc Failures Refael Hassin1 · R. Ravi2 · F. Sibel Salman3 · Danny Segev4 Received: 13 March 2019 / Accepted: 24 February 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We introduce and study the maximum reliability coverage problem, where multiple facilities are to be located on a network whose arcs are subject to random failures. Our model assumes that arcs fail independently with non-uniform probabilities, and the objective is to locate a given number of facilities, aiming to maximize the expected demand serviced. In this context, each demand point is said to be serviced (or covered) when it is reachable from at least one facility by an operational path. The main contribution of this paper is to establish tight bounds on the approximability of maximum reliability coverage on bidirected trees as well as on general networks. Quite surprisingly, we show that this problem is NP-hard on bidirected trees via a carefully-constructed reduction from the partition problem. On the positive side, we make use of approximate dynamic programming ideas to devise an FPTAS on bidirected trees. For general networks, while maximum reliability coverage is (1 − 1∕e + 𝜖)-inapproximable as an extension of the max k-cover problem, even estimating its objective value is #P-complete, due to generalizing certain network reliability problems. Nevertheless, we prove that by plugging-in a sampling-based additive estimator into the standard greedy algorithm, a matching approximation ratio of 1 − 1∕e − 𝜖 can be attained. Keywords Facility location · Random arc failures · FPTAS · Dynamic programming · Hardness
1 Introduction In this paper, we introduce and study a multiple facility location problem on a network whose arcs are subject to random failures. Specifically, a given number of facilities should be located at the nodes of a directed graph, whose arcs may fail independently with prespecified probabilities. The objective is to maximize the * Danny Segev [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
expected demand serviced, where the latter expectation is taken over the possible network realizations, and a demand point is said to be serviced (or covered) when it is reachable from at least one facility by an operational path. Problems of this nature find practical applications in computer and telecommunications networks, where arcs represent communication links. In these contexts, arc failures may occur due to a random disruption in communication or due to transmission equipment malfunctions, and service providers are to be located at selected nodes to guarantee the most reliable data services to the demand nodes. As facility location problems subject to stochastic network failures have attracted a great deal of attention in the last two decades, it is beyond the scope of this paper to provide an exhaustive overview of previous work. To
Data Loading...
