Starting with an arbitrary point in a finite metric space, repeatedly select a point maximizing its distance to the selected set. Maintain each point's distance to its nearest selected center; each new center updates all those distances, giving distance evaluations for centers.
For the metric k-center problem, let be the final covering radius and add a point realizing to the selected centers. Every pair among these points has distance at least : at each selection the current maximum distance is at least its final value. If the optimum radius is , two of these points belong to the same optimal radius- closed ball, so the triangle inequality gives . The case is already optimal. This proves a factor-two approximation algorithm.
Articles by others on the same topic
Farthest-first traversal is a strategy used primarily in clustering and data sampling algorithms. It is designed to efficiently explore data points in a dataset by selecting points that are as far away from existing selected points as possible. This approach is often used in scenarios where you want to create a representative sample of data or construct clusters that are well-distributed across the data space.