In the k-median problem we are given sets of facilities and customers, and distances between them. For a given set F of facilities, the cost of serving a customer u is the minimum distance between u and a facility in F. The goal is to find a set F of k facilities that minimizes the sum, over all customers, of their service costs. Following the work of Mettu and Plaxton, we study the incremental medians problem, where k is not known in advance. An incremental algorithm produces a nested sequence of facility sets F1 ⊆ F2 ⊆ … ⊆ Fn, where |Fk|=k for each k. Such an algorithm is called c-cost-competitive if the cost of each Fk is at most c times the optimum k-median cost. We give improved incremental algorithms for the metric version of this problem.
