An approximation algorithm for Robust k-product facility location problem with linear penalties

Expand
  • 1. School of Mathematics and Statistic, Hunan Normal University, Changsha 410081, Hunan, China
    2. College of Information Science and Engineering, Hunan First Normal University, Changsha 410205, Hunan, China

Received date: 2020-05-11

  Online published: 2021-12-11

Abstract

A $k$-product facility location problem can be described as follows. There is a set of customers and a set of potential sites where facility can be set up. There are $k$ different products. Each customer needs to be served with all of the $k$ different products and each facility can be set up to provide exact one product. The problem is to select a set of facility to be set up and determine an assignment for each customer to a set of $k$ facilities to provide it with $k$ distinct products. It is assumed that the capacity of any facility is unlimited and there is a non-negative cost for shipping products between each pair of locations. The aim is to minimize the sum of the setup costs and the shipping costs from facilities to customers. For simplicity, we denote the problem by $k$-PUFLP. When the cost of setting up any facility is zero, we denote by $k$-PUFLPN. When $k\geq 3$, the approximation ratio of an existing algorithm is improved to $\frac{3k}{2}-\frac{3}{2}$. When a maximum of $q$ customers are allowed to be unserved, we call it Robust $k$-product facility location problem. For this problem, we addressed an approximation algorithm with an approximate ratio of $\frac{3k}{2}-\frac{3}{2}$. For the Robust $k$-product facility location problem of linear penalties, by considering both outliers and penalty we also designed a $\frac{3k}{2}-\frac{3}{2}$ approximation algorithm.

Cite this article

Xiaowei LI, Xiayan CHENG, Rongheng LI . An approximation algorithm for Robust k-product facility location problem with linear penalties[J]. Operations Research Transactions, 2021 , 25(4) : 31 -44 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.04.003

References

1 Shmoys D B, Tardos E, Aardal K I. Approximation algorithms for facility location problems[C]//Proceedings of STOC, 1997: 265-274.
2 Jain K , Vazirani V V . Approximation algorithms for metric facility location and $ k $-median problems using the primal-dual schema and Lagrangian relaxation[J]. Journal of the ACM, 2001, 48, 274- 296.
3 Jain K, Mahdian M, Saberi A. A new greedy approach for facility location problems[C]//Proceedings of STOC, 2002: 731-740.
4 Mahdian M, Ye Y, Zhang J. Improved approximation algorithms for metric facility location problems[C]//Proceedings of APPROX, 2002: 229-242.
5 Li S . A 1.488 approximation algorithm for the uncapacitated facility location problem[J]. Information and Computation, 2013, 222, 45- 58.
6 Guha S , Khuller S . Greedy strikes back: Improved facility location algorithms[J]. Journal of Algorithm, 1999, 31, 228- 248.
7 Charikar M, Khuller S, Mount D M, et al. Algorithms for facility location problem with outliers[C]//Proceedings of SODA, 2001: 642-651.
8 Xu G , Xu J . An improved approximation algorithm for uncapacitated facility location problem with penalties[J]. Journal of Combinatorial Optimization, 2008, 17, 424- 436.
9 Li Y , Du D , Xiu N , et al. Improved approximation algorithms for the facility location problems with linear/submodular penalties[J]. Algorithmica, 2015, 73, 460- 482.
10 Aardal K I , Chudak F A , Shmoys D B . A 3-approximation algorithm for the $ k $-level uncapacitated facility location problem[J]. Information Processing Letters, 1999, 72, 161- 167.
11 Ageev A , Ye Y , Zhang J . Improved combinatorial approximation algorithms for the $ k $-level facility location problem[J]. SIAM Journal on Discrete Mathematics, 2004, 18, 207- 217.
12 Li R , Huang H C , Huang J . Heuristic algorithms for general $ k $-level facility location problems[J]. Journal of the Operational Research Society, 2013, 64 (1): 106- 113.
13 Huang H C , Li R . A $ k $-product uncapacitated facility location problem[J]. European Journal of Operational Research, 2008, 185, 552- 562.
14 易斌, 李荣珩. 一个关于$ k $-种产品选址问题的近似算法[J]. 计算机工程与应用, 2008, 44, 97- 99.
Outlines

/