Journal
OPTIMIZATION LETTERS
Volume 15, Issue 6, Pages 2053-2065Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s11590-021-01701-8
Keywords
Facility location problem; Outliers; Approximation algorithm; Primal-dual
Funding
- National Natural Science Foundation of China [11871081, 12001523, 11971349]
- Beijing Natural Science Foundation Project [Z200002]
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available