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 $F_1\subseteq F_2\subseteq \cdots \subseteq F_n$, where each $F_k$ contains at most $k$ facilities. This sequence is said to be $\delta$-competitive if the cost of each $F_k$ is at most $\delta$ 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.