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 . DOI: 10.1007/s40305-024-00555-y

[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)