In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm maintains 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. For Facility Location, we consider the case of uniform facility costs, where the cost of opening a facility is the same for all points, and present the first incremental algorithm which achieves a constant performance ratio. Using this algorithm as a building block, we obtain the first incremental algorithm for k-Median which achieves a constant performance ratio using O(k) medians. The algorithm is based on a novel merge rule which ensures that the algorithm's configuration monotonically converges to the optimal facility locations according to a certain notion of distance. Using this property, we reduce the general case to the special case when the optimal solution consists of a single facility.
展开▼
