Approximation Algorithm for the k-Product Uncapacitated Facility Location Problem with Penalties

doi:10.1007/s40305-023-00478-0

Abstract

Abstract: In the k-product uncapacitated facility location problem with penalties, we are given a set of demand points where clients are located and a set of potential sites where facilities with unlimited capacities can be opened. There are k different kinds of products to be supplied by a set of open facilities. Each open facility can supply only a distinct product with a non-negative fixed cost determined by the product it wants to supply. Each client is either supplied with k kinds of products by a set of k different open facilities or completely rejected. There is a non-negative service cost between each pair of locations and also a penalty cost for each client if its service is rejected. These service costs are assumed to be symmetric and satisfy the triangle inequality. The goal is to select a set of clients to reject their service and then choose a set of facilities to be opened to service the remaining clients so that the total cost of opening facilities, servicing the clients, and the penalty is minimized. We address two different integer programs to describe the problem. Based on the linear programming rounding technique, we propose a (2k +1)-approximation algorithm for this problem.

Key words: k-product, Facility location, Penalty, LP-rounding, Approximation algorithm

CLC Number:

90B80
90C10

Pei-Jia Yang, Wen-Chang Luo. Approximation Algorithm for the k-Product Uncapacitated Facility Location Problem with Penalties[J]. Journal of the Operations Research Society of China, 2025, 13(1): 287-296.

TrendMD

References

[1] Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: the 29th Annual ACM Symposium on Theory of Computing, pp. 265-274. ACM Press, Berlin (1997)
[2] Jain, K., Vazirani, V.V.: Primal-dual approximation algorithms for metric facility location and kmedian problems. In: The 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 2-13. ACM Press, USA (1999)
[3] Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31, 228-248(1999)
[4] Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 378-388. ACM Press, USA (1999)
[5] Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. J. Algorithms 37(1), 146-188(2000)
[6] Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problem. In: the 34th ACM Symposium on Theory of Computing (STOC), pp. 731-740. ACM Press, New York (2002)
[7] Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 229-242. ACM Press, Berlin (2002)
[8] Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33(1), 1-25(2004)
[9] Byrka, J., Aardal, K.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 39(6), 2212-2231(2010)
[10] Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45-58(2013)
[11] Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximation for maximizing submodular set functions II. Math. Program. Study 8, 73-87(1978)
[12] Ardal, K., Chudak, F.A., Shmoys, D.B.: A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inf. Process. Lett. 72(5/6), 161-167(1999)
[13] Klincewicz, J.G., Luss, H., Rosenberg, E.: Optimal and heuristic algorithms for multiproduct uncapacitated facility location. Eur. J. Oper. Res. 26(2), 251-258(1986)
[14] Klincewicz, J.G., Luss, H.: A dual-based algorithm for multiproduct uncapacitated facility location. Transp. Sci. 21(3), 198-206(1987)
[15] Lee, C.Y.: An optimal algorithm for the multiproduct capacitated facility location problem with a choice of facility type. Comput. Oper. Res. 18(2), 167-182(1991)
[16] Lee, C.Y.: A cross decomposition algorithm for a multiproduct-multitype facility location problem. Comput. Oper. Res. 20, 527-540(1993)
[17] Mazzola, J.B., Neebe, A.W.: Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type. Eur. J. Oper. Res. 115(2), 285-299(1999)
[18] Huang, H.C., Li, R.: A k-product uncapacitated facility location problem. Eur. J. Oper. Res. 185, 552-562(2008)
[19] Nezhad, A.M., Manzour, H., Salhi, S.: Lagrangian relaxation heuristics for the uncapacitated singlesource multi-product facility location problem. Int. J. Prod. Econ. 145, 713-723(2013)
[20] Yang, M.M., Huang, Y.K., Dai, Y.H.: Linear relaxation solution based heuristics for a class of multiproduct facility location problems. Oper. Res. Trans. 23(3), 15-26(2019)
[21] Charikar, M., Khuller, S., Mount, D., Narasimhan, G.: Algorithms for facility location problems with outliers. In: 12th ACM-SIAM Symposium on Discrete Algorithms, pp. 642-651. ACM Press, Washington (2001)
[22] Xu, G., Xu, J.: An LP rounding algorithm for approximating uncapacitated facility location problem with penalties. Inf. Process. Lett. 94(3), 119-123(2005)
[23] Fang, S.C., Puthenpura, S.: Linear Optimization and Extensions: Theory and Algorithms. Prentice Hall, Hoboken (1993)