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

被引：2

作者：

Luo, Hang ^{[1
]}

Han, Lu ^{[2
]}

Shuai, Tianping ^{[2
]}

Wang, Fengmin ^{[3
]}

机构：

[1] Beijing Univ Posts & Telecommun, Int Sch, Beijing 100876, Peoples R China

[2] Beijing Univ Posts & Telecommun, Sch Sci, Beijing 100876, Peoples R China

[3] Beijing Jinghang Res Inst Comp & Commun, Beijing 100074, Peoples R China

来源：

TSINGHUA SCIENCE AND TECHNOLOGY | 2024年 / 29卷 / 06期

关键词：

Heuristic algorithms; Approximation algorithms; priority facility location; primal-dual; approximation algorithm;

D O I：

10.26599/TST.2023.9010152

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：1694 / 1702

页数：9

共 17 条

[1]

Arya V., 2001, LOCAL SEARCH HEURIST, V21, P29

[2] AN OPTIMAL BIFACTOR APPROXIMATION ALGORITHM FOR THE METRIC UNCAPACITATED FACILITY LOCATION PROBLEM [J].

Byrka, Jaroslaw ;

Aardal, Karen .

SIAM JOURNAL ON COMPUTING, 2010, 39 (06) :2212-2231

[3]

Charikar M, 2001, SIAM PROC S, P642

[4] Improved approximation algorithms for the uncapacitated facility location problem [J].

Chudak, FA ;

Shmoys, DB .

SIAM JOURNAL ON COMPUTING, 2003, 33 (01) :1-25

[5] Greedy facility location algorithms analyzed using,dual fitting with factor-revealing LP [J].

Jain, K ;

Mahdian, M ;

Markakis, E ;

Saberi, A ;

Vazirani, VV .

JOURNAL OF THE ACM, 2003, 50 (06) :795-824

[6] Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation [J].

Jain, K ;

Vazirani, VV .

JOURNAL OF THE ACM, 2001, 48 (02) :274-296

[7]

Jain K., 2002, P 34 ANN ACM S THEOR, DOI [DOI 10.1145/509907.510012, 10.1145/509907.510012, DOI 10.1016/J.0RL.2006.03.0]

[8] Analysis of a local search heuristic for facility location problems [J].

Korupolu, MR ;

Plaxton, CG ;

Rajaraman, R .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2000, 37 (01) :146-188

[9] Approximation algorithms for the stochastic priority facility location problem [J].

Li, Gaidi ;

Wang, Zhen ;

Wu, Chenchen .

OPTIMIZATION, 2013, 62 (07) :919-928

[10] A 1.488 approximation algorithm for the uncapacitated facility location problem [J].

Li, Shi .

INFORMATION AND COMPUTATION, 2013, 222 :45-58

← 1 2 →