The uncapacitated facility location problem asks us to select
locations for facilities on a network so as to minimize the total cost
of facilities and customer travel to facilities. This problem is
NP-hard and recently a linear programming relaxation was shown to give
constant approximations for it as well as good approximations for
other related problems. A simple local search heuristic for these
problems has been known for decades but no bound on its performance
was known. In this talk we present a result of Koropolu, Plaxton and
Rajamaran (SODA '98), who show that local search comes within a
constant factor of the LP relaxation when applied to these problems.
(These are results from a paper in SODA 1998 by Koropolu, Plaxton and
Rajamaran.)