98-30: Analysis of a Local Search Heuristic for Facility Location Problems

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