Approximation Scheme for the Single-Client Capacitated Facility Location Problem With Operational Cost Budget Constraint

doi:10.1007/s40305-024-00555-y

Abstract

Abstract: We investigate the single-client capacitated facility location problem with operational cost budget constraint. Specifically speaking, we are given a single client with demand, a set of potential facilities with capacities, and a positive integer specifying the operational cost budget. For each open facility, one should pay its opening cost and operational cost. For each open facility to service the client, one should pay the service cost. The objective is to open enough facilities serving the client’s demand and satisfying the capacity and operational cost budget constraints while minimizing the sum of opening and service costs. In this paper, based on dynamic programming and sparse techniques, we derive a fully polynomial time approximation scheme (FPTAS) with violating the operational cost budget constraint at most an arbitrarily small factor or claim that there is no feasible solution.

Key words: Single client, Capacitated facility location, Dynamic programming, Sparse, Approximation scheme

CLC Number:

90B80

Lu Chen, Zheng Chen, Long Wan, Wen-Chang Luo. Approximation Scheme for the Single-Client Capacitated Facility Location Problem With Operational Cost Budget Constraint[J]. Journal of the Operations Research Society of China, 2026, 14(2): 687-699.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00555-y

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I2/687

References

[1] Aggarwal, A., Louis, A., Bansal, M., Garg, N., Gupta, N., Gupta, S., Jain, S.: A 3-approximation algorithm for the facility location problem with uniform capacities. Math. Program. 141(1–2), 527– 547(2013)
[2] Aardal, K., van den Berg, P.L., Gijswijt, D., Li, S.: Approximation algorithms for hard capacitated k-facility location problems. Eur. J. Oper. Res. 242(2), 358–368(2015)
[3] Bansal, M., Garg, N., Gupta, N.: A 5-approximation for capacitated facility location. In: AlgorithmsESA 2012: Proceedings 20, pp. 133-144. Springer Berlin Heidelberg (2012)
[4] Byrka, J., Fleszar, K., Rybicki, B., Spoerhase, J.: Bi-factor approximation algorithms for hard capacitated k-median problems. In: Proceedings of the twenty-sixth annual ACM-SIAM Symposium on Discrete algorithms, pp. 722-736. Society for Industrial and Applied Mathematics (2014)
[5] Cornuéjols, G., Nemhauser,G.L., Wolsey, L.A.: Discrete location theory. In: The uncapacitated facility location problem. pp.119–171. New York. Wiley (1990)
[6] Charikar, M., Guha, S., Tardos, É., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem.In:Proceedingsofthethirty-firstannualACMSymposiumon theory ofcomputing, pp. 1-10(1999)
[7] Chudak, F.A., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102, 207–222(2005)
[8] Drezner, Z., Hamacher, H.W.:(Eds.). Facility location: applications and theory. Springer Science & Business Media (2004)
[9] Grover, S., Gupta, N., Khuller, S.: LP-based approximation for uniform capacitated facility location problem. Discret. Optim. 45, 100723(2022)
[10] Herer, Y.T., Rosenblatt, M.J., Hefter, I.: Fast algorithms for single-sink fixed charge transportation problems with applications to manufacturing and transportation. Transp. Sci. 30(4), 276–290(1996)
[11] Hsu, V.N., Lowe, T.J., Tamir, A.: Structured p-facility location problems on the line solvable in polynomial time. Oper. Res. Lett. 21(4), 159–164(1997)
[12] Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48(2), 274–296(2001)
[13] Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing, pp. 731-740(2002)
[14] Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795–824(2003)
[15] 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)
[16] Levi, R., Shmoys, D.B., Swamy, C.: LP-based approximation algorithms for capacitated facility location. Math. Program. 131(1–2), 365–379(2012)
[17] Mahdian, M., PÈl, M.: Universal facility location. In: 11th Annual European Symposium, pp. 409– 421. Springer, Berlin Heidelberg (2003)
[18] Nickel, S., Puerto, J.: Location theory: a unified approach. Springer Science & Business Media (2006)
[19] Pál, M., Tardos, È., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 329–338. IEEE (2001)
[20] Shmoys, D.B., Tardos, È., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing, pp. 265–274. (1997)
[21] Zhang, J., Chen, B., Ye, Y.: A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res. 30(2), 389–403(2005)
[22] Zhang, P.: A new approximation algorithm for the k-facility location problem. Theoret. Comput. Sci. 384(1), 126–135(2007)