A 3-approximation algorithm for the facility location problem with uniform capacities

We consider the facility location problem where each facility can serve at most U clients. We analyze a local search algorithm for this problem which uses only the operations of add, delete and swap and prove that any locally optimum solution is no more than 3 times the global optimum. This improves on a result of Chudak and Williamson who proved an approximation ratio of for the same algorithm. We also provide an example which shows that any local search algorithm which uses only these three operations cannot achieve an approximation guarantee better than 3.