New variations of the maximum coverage facility location problem
Consider a competitive facility location scenario where, given a set U of n users and a set F of m facilities in the plane, the objective is to place a new facility in an appropriate place such that the number of users served by the new facility is maximized. Here users and facilities are considered as points in the plane, and each user takes service from its nearest facility, where the distance between a pair of points is measured in either L1 or L2 or L∞ metric. This problem is also known as the maximum coverage (MaxCov) problem. In this paper, we will consider the k-MaxCov problem, where the objective is to place k (⩾1) new facilities such that the total number of users served by these k new facilities is maximized. We begin by proposing an O(nlogn) time algorithm for the k-MaxCov problem, when the existing facilities are all located on a single straight line and the new facilities are also restricted to lie on the same line. We then study the 2-MaxCov problem in the plane, and propose an O(n2) time and space algorithm in the L1 and L∞ metrics. In the L2 metric, we solve the 2-MaxCov problem in the plane in O(n3logn) time and O(n2logn) space. Finally, we consider the 2-Farthest-MaxCov problem, where a user is served by its farthest facility, and propose an algorithm that runs in O(nlogn) time, in all the three metrics.
Volume (Year): 224 (2013)
Issue (Month): 3 ()
|Contact details of provider:|| Web page: http://www.elsevier.com/locate/eor|
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Cabello, S. & Díaz-Báñez, J.M. & Langerman, S. & Seara, C. & Ventura, I., 2010. "Facility location problems in the plane based on reverse nearest neighbor queries," European Journal of Operational Research, Elsevier, vol. 202(1), pages 99-106, April.
- Eiselt, H. A. & Laporte, G., 1989. "Competitive spatial models," European Journal of Operational Research, Elsevier, vol. 39(3), pages 231-242, April.
- Qian Wang & Rajan Batta & Christopher Rump, 2002. "Algorithms for a Facility Location Problem with Stochastic Customer Demand and Immobile Servers," Annals of Operations Research, Springer, vol. 111(1), pages 17-34, March.
- Abellanas, Manuel & Lillo, Isabel & Lopez, M Dolores & Rodrigo, Javier, 2006. "Electoral strategies in a dynamical democratic system. Geometric models," European Journal of Operational Research, Elsevier, vol. 175(2), pages 870-878, December.
- Abellanas, Manuel & López, M Dolores & Rodrigo, Javier, 2010. "Searching for equilibrium positions in a game of political competition with restrictions," European Journal of Operational Research, Elsevier, vol. 201(3), pages 892-896, March.
- Plastria, Frank, 2001. "Static competitive facility location: An overview of optimisation approaches," European Journal of Operational Research, Elsevier, vol. 129(3), pages 461-470, March.
When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:224:y:2013:i:3:p:477-485. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Shamier, Wendy)
If references are entirely missing, you can add them using this form.