Discover the SciOpen Platform and Achieve Your Research Goals with Ease.
Search articles, authors, keywords, DOl and etc.
In this paper, we propose the Priority Facility Location Problem with Outliers (PFLPO), which is a generalization of both the Facility Location Problem with Outliers (FLPO) and Priority Facility Location Problem (PFLP). As our main contribution, we use the technique of primal-dual to provide a 3-approximation algorithm for the PFLPO. We also give two heuristic algorithms. One of them is a greedy-based algorithm and the other is a local search algorithm. Moreover, we compare the experimental results of all the proposed algorithms in order to illustrate their performance.
J. Byrka and K. Aardal, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM J. Comput., vol. 39, no. 6, pp. 2212–2231, 2010.
F. A. Chudak and D. B. Shmoys, Improved approximation algorithms for the uncapacitated facility location problem, SIAM J. Comput., vol. 33, no. 1, pp. 1–25, 2003.
K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, J. ACM, vol. 48, no. 2, pp. 274–296, 2001.
K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM, vol. 50, no. 6, pp. 795–824, 2003.
M. R. Korupolu, C. G. Plaxton, and R. Rajaraman, Analysis of a local search heuristic for facility location problems, J. Algoritms., vol. 37, no. 1, pp. 146–188, 2000.
G. Li, Z. Wang, and C. Wu, Approximation algorithms for the stochastic priority facility location problem, Optimization, vol. 62, no. 7, pp. 919–928, 2013.
F. Wang, D. Xu, and C. Wu, Approximation algorithms for the priority facility location problem with penalties, J. Syst. Sci. Complex., vol. 28, no. 5, pp. 1102–1114, 2015.
753
Views
240
Downloads
0
Crossref
0
Web of Science
0
Scopus
0
CSCD
Altmetrics
The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).