Euclidean K-Center Problem

Question

My google searches have brought me to rather long papers explaining the Euclidean K-Center problem.

Can someone please provide a high-level explanation?

Thanks.

Answer 1

Given $n$ houses represented as points in the plane, find the optimal location of $k$ firestations to protect them, optimal in the sense that these locations minimimize the furthest distance between a house and a firestation. For $k=1$, the optimal is the center of the minimum circumscribing circle.

Finding an exact solution is NP-hard, but there are approximation algorithms, unfortunately none that can beat a factor of $2$.