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

作者：Aggarwal Ankit; Louis Anand; Bansal Manisha; Garg Naveen^*; Gupta Neelima; Gupta Shubham; Jain Surabhi

来源：Mathematical Programming, 2013, 141(1-2): 527-547.

DOI：10.1007/s10107-012-0565-4

• Facility location
• Local search
• Approximation algorithms
• 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.

• 出版日期2013-10