# Euclidean K-Center Problem

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.

-

## 1 Answer

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$.

-
If the houses are randomly placed, then the center is still the optimum? – Kevin Meredith Jan 16 '13 at 18:25
Yes, random placement is not directly relevant. – Joseph O'Rourke Jan 17 '13 at 0:38