An approximation algorithm for the Euclidean incremental median problem

In the incremental version of the k-median problem, we find a sequence of facility sets F1⊆F2⊆⋯⊆Fn, where each Fk contains at most k facilities. This sequence is said to be δ-competitive if the cost of each Fk is at most δ times the optimum cost of k facilities. The best deterministic (randomized) algorithm available for the metric space has a competitive ratio of 8 (7.656). The best one for the one-dimensional problem finds a 5.828-competitive sequence. We give a 7.076-competitive solution for the high-dimensional Euclidean space.