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...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2013-10, Vol.141 (1-2), p.527-547
Main Authors: Aggarwal, Ankit, Louis, Anand, Bansal, Manisha, Garg, Naveen, Gupta, Neelima, Gupta, Shubham, Jain, Surabhi
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Calculus of Variations and Optimal Control
Optimization
Clients
Combinatorics
Costs
Full Length Paper
Guarantees
Mathematical analysis
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical programming
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Optimization
Position (location)
Search algorithms
Studies
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-012-0565-4