A note on LP-based approximation algorithms for capacitated facility location problem

In the capacitated facility location problem, we are given a set F of potential facilities and a set D of clients, where each facility has a capacity and an open cost, and each client has a demand to be served by the facilities with service costs. The goal is to open some facilities in F and assign all clients in D to these open facilities such that the total cost is minimum. Based on the natural integer programming formulation, Levi et al. [8] presented an LP-based 5-approximation algorithm for this problem under the assumption that the facility costs are uniform. Based on the same integer programming formulation, we remove the uniformity assumption and present an ( R+root R-2+8R/2 + 3)-approximation algorithm for the capacitated facility location problem, where R is the upper bound of the ratio between facility costs. Our result is a slight extension of the corresponding result in [8], as when R = 1 the worst-case ratio of our algorithm is R+root R-2+8R/2 + 3 = 5. (c) 2022 Elsevier B.V. All rights reserved.