Local search heuristic for k-median and facility location problems

In this paper, we analyze local search heuristics for the k-median and facility location problems. We define the {\em locality gap\/} of a local search procedure 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 exactly 5. When we permit p facilities to be swapped simultaneously then the locality gap of the local search procedure is exactly 3+2/p. This is the first analysis of 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 exactly 3. This improves the 5 bound of Korupolu et al. We also consider a capacitated facility location problem where each facilitym has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new operation which opens one or more copies of a facility and drops zero or more facilities. We prove that local search which permits this new operation has a locality gap between 3 and 4.