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 + R 2 + 8 R 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 + R 2 + 8 R 2 + 3 = 5. [ABSTRACT FROM AUTHOR]