Answers are grounded in this paper and cite their sources.
In this paper we define and discuss the following problem which we call the maximum coverage location problem. A transportation network is given together with the locations of customers and facilities. Thus, for each customer i, a radius rᵢ is known such that customer i can currently be served by a facility which is located within a distance of rᵢ from the location of customer i. We consider the problem from the point of view of a new company which is interested in establishing new facilities on the network so as to maximize the company’s “share of the market.” Specifically, assume that the company gains an amount of wᵢ in case customer i decides to switch over to one of the new facilities. Moreover, we assume that the decision to switch over is based on proximity only, i.e., customer i switches over to a new facility only if the latter is located at a distance less than rᵢ from i. The problem is to locate p new facilities so as to maximize the total gain. The maximum coverage problem is a relatively complicated one even on tree-networks. This is because one aspect of the problem is the selection of the subset of customers to be taken over. Nevertheless, we present an O ( n² p ) algorithm for this problem on a tree. Our approach can be applied to other similar problems which are discussed in the paper.
No takes yet. Share an insight, caveat, or question.
Megiddo et al. (1983) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: