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

作　　者：Hang Luo Lu Han Tianping Shuai Fengmin Wang 

机构地区：[1]International School,Beijing University of Posts and Telecommunications,Beijing 100876,China [2]School of Science,Beijing University of Posts and Telecommunications,Beijing 100876,China [3]Beijing Jinghang Research Institute of Computing and Communication,Beijing 100074,China

出　　处：《Tsinghua Science and Technology》2024年第6期1694-1702,共9页清华大学学报自然科学版（英文版）

基　　金：supported by the Beijing Municipal Natural Science Foundation(No.Z220004);the National Natural Science Foundation of China(Nos.12371321,12171051,and 12171052);the Research Innovation Fund for College Students of Beijing University of Posts and Telecommunications.

摘　　要：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.

关 键 词：priority facility location PRIMAL-DUAL approximation algorithm 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]