Analysis of a local search heuristic for facility location problems

In this paper, we study approximation algorithms for several NP-hard facility location problems. We prove that a simple local starch heuristic yields polynomial time constant-factor approximation bounds for metric versions of the uncapacitated k-median problem and the uncapacitated facility location problem. (For the k-median problem, our algorithms require a constant-factor blowup in the parameter k.) This local search heuristic was first proposed several decades ago and has been shown to exhibit good practical performance in empirical studies. We also extend the above results to obtain constant-factor approximation bounds for the metric versions of capacitated k-median and facility location problems. (C) 2000 Academic Press.