An Approximation Algorithm For The K-level Facility Location Problem With Outliers

In this paper,we study the k-level facility location problem with outliers(k-LFLPWO),which is a generalization of the k-level facility location problem(k-LFLP)and the uncapaci-tated facility location problem with outliers(UFLPWO).We research this problem with a high practical value which can improve social productivity and economic efficiency.In the k-level facility location problem with outliers,there are given k facility location sets,a set of clients and a non-negative integer q(q<n),n is the total number of clients,q is the total number of outliers which.Every facility set has a different level which belongs to {1,2,…,k}.For any facility i which can be opened,the corresponding opening cost is fi>0.For any client j,it receives the service from the facility i and generates the connecting cost cij>0.We wish to open some facilities in each facility location set and connect at least n-q clients to open facilities from level 1 to level k,such that the total cost including opening costs and connecting costs is minimized.For the k-level facility location problem with outliers,we use the technique of primal-dual and get a 6-approximation algorithm.The k-level facility location problem with outliers is NP-hard.There is no exact algorithm can be found in polynomial time under the assumption of P?NP.So approximation algorith-m is usually used for those problem.The technique of primal-dual is one of the most useful methods in approximation algorithm design.This paper introduces the primal-dual algorithm for k-level facility location problem,and uses the robustness of the primal-dual algorithm to transplant the algorithm to the k-level facility location problem with outliers.Based on the liner program relaxation of the k-LFLPWO,we design a primal-dual algorithm for the corresponding dual program and give a 6-approximation algorithm for this problem.This is the first constant approximation ratio algorithm for this problem so far.