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 an extension of the well-known k-level facility location problem (k-LFLP). In the k-LFLPWO, we are given k facility location sets, a client location set of cardinality n and a non-negative integer q < n. Every facility location set has a different level which belongs to {1, 2,..., k}. For any facility location, there is an opening cost. For any two locations, there is a connecting cost. We wish to connect at least n - q clients to opened facilities from level 1 to level k, such that the total cost including opening costs and connecting costs is minimized. Our main contribution is to present a 6-approximation algorithm, which is based on the technique of primal-dual, for the k-LFLPWO.

Automated summary

This paper studies the k-level facility location problem with outliers and proposes a 6-approximation algorithm based on primal-dual technique. The goal is to minimize the total cost of connecting clients to facilities of different levels.