Simpler Analyses of Local Search Algorithms for Facility Location

We study local search algorithms for metric instances of facility location problems: the uncapacitated facility location problem (UFL), as well as uncapacitated versions of the k-median, k-center and kmeans problems. All these problems admit natural local search heuristics: for example, in the UFL problem the natural moves are to open a new facility, close an existing facility, and to swap a closed facility for an open one; in k-medians, we are allowed only swap moves. The local-search algorithm for k-median was analyzed by Arya et al. (SIAM J. Comput. 33(3):544-562, 2004), who used a clever “coupling” argument to show that local optima had cost at most constant times the global optimum. They also used this argument to show that the local search algorithm for UFL was 3-approximation; their techniques have since been applied to other facility location problems