Metric K-Center

The metric k-center problem is a classical combinatorial optimization problem that asks for a set of k vertices, out of a larger set of points with known pairwise distances, such that the greatest distance from any point to its nearest chosen vertex is as small as possible; a standard illustration frames it as choosing k warehouse locations among n cities so as to minimize the worst-case distance any city must travel to reach its nearest warehouse. The problem is NP-hard, so no known algorithm solves it exactly in polynomial time, but several polynomial-time approximation algorithms are known, the best of which guarantees a solution no more than twice the optimal value. These include a simple greedy algorithm that repeatedly picks the point farthest from the centers already chosen, a farthest-first traversal running in O(nk) time with a 2-approximation guarantee, the Shmoys algorithm, which selects centers at random from vertices beyond a distance threshold, and the Gonzalez algorithm, which achieves the same running time without needing to guess the optimal solution size in advance; a further CDS algorithm trades a weaker 3-approximation guarantee for better practical performance. The problem is directly relevant to facility location and clustering applications. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/