## DIMACS TR: 98-30

## Analysis of a Local Search Heuristic for Facility Location
Problems

### Authors: Madhukar R. Korupolu, C. Greg Plaxton and Rajmohan Rajaraman

**
ABSTRACT
**

In this paper, we study approximation algorithms for several NP-hard
facility location problems. We prove that a simple local search
heuristic yields polynomial-time constant-factor approximation bounds
for the 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.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-30.ps.gz

DIMACS Home Page