ALCOMFT-TR-03-156

Dimitris Fotakis
Incremental Algorithms for Facility Location and k-Median
Patras. Work packages 1 and 4. December 2003.

Abstract: In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm must maintain a good solution by either adding each new demand to an existing cluster or placing it in a new singleton cluster. The algorithm can also merge some of the existing clusters at any point in time. We present the first incremental algorithm for Facility Location which achieves a constant performance ratio and the first incremental algorithm for k-Median which achieves a constant performance ratio using O(k) medians, thus resolving an open question of [Charikar, Panigrahy, STOC 2001]. Our algorithm is based on a merge rule which ensures that the algorithm's configuration monotonically converges to each optimal facility according to a certain notion of distance. Using this property, we reduce the general case to the special case that the optimal solution consists of a single facility.

Postscript file: ALCOMFT-TR-03-156.ps.gz (120 kb).