AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (2.6 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Approximation and Heuristic Algorithms for the Priority Facility Location Problem with Outliers

International School, Beijing University of Posts and Telecommunications, Beijing 100876, China
School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
Beijing Jinghang Research Institute of Computing and Communication, Beijing 100074, China
Show Author Information

Abstract

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.

Keywords

priority facility locationprimal-dualapproximation algorithm

References

[1]
P. B. Mirchandani and R. L. Francis, Discrete location theory. New York, NY, USA: John Wiley & Sons, 1990.
[2]
D. B. Shmoys, E. Tardos, and K. Aardal, Approximation algorithms for facility location problems, in Proc. of the 29th Annual ACM Symposium on Theory of Computing, El Paso, TX, USA, 1997, pp. 265–274.
Crossref
[3]
S. Li, A 1.488 approximation algorithm for the uncapacitated facility location problem, Inf. Comput., vol. 222, pp. 45–58, 2013.
Crossref
[4]
M. Sviridenko, An improved approximation algorithm for the metric uncapacitated facility location problem, in Proc. of the 9th Int. Conf. on Integer Programming and Combinatorial Optimization, Copenhagen, Denmark, 2002. pp. 240–257,
Crossref
[5]

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.
Crossref Google Scholar
[6]

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.
Crossref Google Scholar
[7]

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.
Crossref Google Scholar
[8]

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.
Crossref Google Scholar
[9]
K. Jain, M. Mahdian, and A. Saberi, A new greedyapproach for facility location problems, in Proc. of the 34th Annual ACM Symposium on Theory of Computing, Montréal, Canada, 2002, pp. 731–740.
Crossref
[10]
M. Mahdian, Y. Ye, and J. Zhang, Improved approximation algorithms for metric facility location problems, in Proc. of 5th International Workshop, APPROX 2002, Rome, Italy, 2002, pp. 229–242.
Crossref
[11]
V. Arya, N. Garg, R. Khandekar, A. Meyerson, and K. Munagala, Local search heuristic for k-median andfacility location problems, in Proc. of the 33th Annual ACM Symposium on Theory of Computing, Heraklion, Greece, 2001, pp. 21–29.
Crossref
[12]

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.
Crossref Google Scholar
[13]
M. Charikar, S. Khuller, D. M. Mount, and G. Narasimhan, Algorithms for facility location problems with outliers, in Proc. of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC, USA, 2001, pp. 642–651.
[14]
R. Ravi and A. Sinha, Multicommodity facility location, in Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA, 2004, pp. 342–349.
[15]
M. Mahdian, Facility location and the analysis of algorithms through factor-revealing programs, PhD dissertation, Massachusetts Institute of Technology, Cambridge, MA, USA, 2004.
[16]

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.
Crossref Google Scholar
[17]

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.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 29 Issue 6,
December 2024
Pages 1694-1702
DOI: 10.26599/TST.2023.9010152
Cite this article:
Luo H, Han L, Shuai T, et al. Approximation and Heuristic Algorithms for the Priority Facility Location Problem with Outliers. Tsinghua Science and Technology, 2024, 29(6): 1694-1702. https://doi.org/10.26599/TST.2023.9010152

732

Views

236

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 06 July 2023
Revised: 04 October 2023
Accepted: 04 December 2023
Published: 20 June 2024
© The Author(s) 2024.

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/).
Return