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 o...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.展开更多
基金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.
