A 3-approximation algorithm for the facility location problem with uniform capacities
成果类型：
Article
署名作者：
Aggarwal, Ankit; Louis, Anand; Bansal, Manisha; Garg, Naveen; Gupta, Neelima; Gupta, Shubham; Jain, Surabhi
署名单位：
University System of Georgia; Georgia Institute of Technology; University of Delhi; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; Alphabet Inc.; Google Incorporated; Alphabet Inc.; Google Incorporated
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-012-0565-4
发表日期：
2013
页码：
527-547
关键词：
摘要：
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.