Skip to main content

Local search heuristics for k-median and facility location problems

Publication ,  Conference
Arya, V; Garg, N; Khandekar, R; Meyerson, A; Munagala, K; Pandit, V
Published in: Conference Proceedings of the Annual ACM Symposium on Theory of Computing
January 1, 2001

In this paper, we analyze local search heuristics for the k-median and facility location problems. We define the 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 facility 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.

Duke Scholars

Published In

Conference Proceedings of the Annual ACM Symposium on Theory of Computing

ISSN

0734-9025

Publication Date

January 1, 2001

Start / End Page

21 / 29
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., & Pandit, V. (2001). Local search heuristics for k-median and facility location problems. In Conference Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 21–29).
Arya, V., N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. “Local search heuristics for k-median and facility location problems.” In Conference Proceedings of the Annual ACM Symposium on Theory of Computing, 21–29, 2001.
Arya V, Garg N, Khandekar R, Meyerson A, Munagala K, Pandit V. Local search heuristics for k-median and facility location problems. In: Conference Proceedings of the Annual ACM Symposium on Theory of Computing. 2001. p. 21–9.
Arya, V., et al. “Local search heuristics for k-median and facility location problems.” Conference Proceedings of the Annual ACM Symposium on Theory of Computing, 2001, pp. 21–29.
Arya V, Garg N, Khandekar R, Meyerson A, Munagala K, Pandit V. Local search heuristics for k-median and facility location problems. Conference Proceedings of the Annual ACM Symposium on Theory of Computing. 2001. p. 21–29.

Published In

Conference Proceedings of the Annual ACM Symposium on Theory of Computing

ISSN

0734-9025

Publication Date

January 1, 2001

Start / End Page

21 / 29