We analyze local search heuristics for the metric k-median and facility location problems. We define the locality gap of a local search procedure for a minimization problem as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. For k-median, we show that local search with swaps has a locality gap of 5. Furthermore, if we permit up to p facilities to be swapped simultaneously, then the locality gap is 3+2/p. This is the first analysis of a local search for k-median that provides a bounded performance guarantee with only k medians. This also improves the previous known 4 approximation for this problem. For uncapacitated facility location, we show that local search, which permits adding, dropping, and swapping a facility, has a locality gap of 3. This improves the bound of 5 given by M. Korupolu, C. Plaxton, and R. Rajaraman Analysis of a Local Search Heuristic for Facility Location Problems, Technical Report 98-30, DIMACS, 1998. We also consider a capacitated facility location problem where each facility has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new local search operation which opens one or more copies of a facility and drops zero or more facilities. We prove that this local search has a locality gap between 3 and 4.
%0 Journal Article
%1 DBLP:journals/siamcomp/AryaGKMMP04
%A Arya, Vijay
%A Garg, Naveen
%A Khandekar, Rohit
%A Meyerson, Adam
%A Munagala, Kamesh
%A Pandit, Vinayaka
%D 2004
%J SIAM J. Comput.
%K algorithm approximation facility.location k-median
%N 3
%P 544-562
%R 10.1137/S0097539702416402
%T Local Search Heuristics for k-Median and Facility Location
Problems
%V 33
%X We analyze local search heuristics for the metric k-median and facility location problems. We define the locality gap of a local search procedure for a minimization problem as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. For k-median, we show that local search with swaps has a locality gap of 5. Furthermore, if we permit up to p facilities to be swapped simultaneously, then the locality gap is 3+2/p. This is the first analysis of a local search for k-median that provides a bounded performance guarantee with only k medians. This also improves the previous known 4 approximation for this problem. For uncapacitated facility location, we show that local search, which permits adding, dropping, and swapping a facility, has a locality gap of 3. This improves the bound of 5 given by M. Korupolu, C. Plaxton, and R. Rajaraman Analysis of a Local Search Heuristic for Facility Location Problems, Technical Report 98-30, DIMACS, 1998. We also consider a capacitated facility location problem where each facility has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new local search operation which opens one or more copies of a facility and drops zero or more facilities. We prove that this local search has a locality gap between 3 and 4.
@article{DBLP:journals/siamcomp/AryaGKMMP04,
abstract = {We analyze local search heuristics for the metric k-median and facility location problems. We define the locality gap of a local search procedure for a minimization problem as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. For k-median, we show that local search with swaps has a locality gap of 5. Furthermore, if we permit up to p facilities to be swapped simultaneously, then the locality gap is 3+2/p. This is the first analysis of a local search for k-median that provides a bounded performance guarantee with only k medians. This also improves the previous known 4 approximation for this problem. For uncapacitated facility location, we show that local search, which permits adding, dropping, and swapping a facility, has a locality gap of 3. This improves the bound of 5 given by M. Korupolu, C. Plaxton, and R. Rajaraman [Analysis of a Local Search Heuristic for Facility Location Problems, Technical Report 98-30, DIMACS, 1998]. We also consider a capacitated facility location problem where each facility has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new local search operation which opens one or more copies of a facility and drops zero or more facilities. We prove that this local search has a locality gap between 3 and 4.},
added-at = {2010-03-30T23:04:55.000+0200},
author = {Arya, Vijay and Garg, Naveen and Khandekar, Rohit and Meyerson, Adam and Munagala, Kamesh and Pandit, Vinayaka},
bibsource = {DBLP, http://dblp.uni-trier.de},
biburl = {https://www.bibsonomy.org/bibtex/2b86c92a39bc525b09232425ac00536ee/ytyoun},
doi = {10.1137/S0097539702416402},
interhash = {a8a0d9627470c3e756ad3e5cc826348c},
intrahash = {b86c92a39bc525b09232425ac00536ee},
journal = {SIAM J. Comput.},
keywords = {algorithm approximation facility.location k-median},
number = 3,
pages = {544-562},
timestamp = {2015-06-04T07:10:33.000+0200},
title = {Local Search Heuristics for k-Median and Facility Location
Problems},
volume = 33,
year = 2004
}