# zbMATH — the first resource for mathematics

On the complexity of some common geometric location problems. (English) Zbl 0534.68032
The p-center problem with respect to a metric $$\rho$$ (on the plane) consists in producing p points for a given set of n points to minimize the maximal distance (in the metric $$\rho)$$ from the given points to their respective nearest produced points. The similar p-median problem is to minimize the sum of the considered distances. The main result of the paper states that both, p-center and p-median problem, are NP-hard for two metrics $$\rho =\ell^ 2,\ell^ 1$$. It is also proved that the p- center problem is NP-hard even if approximating it within 15 % for $$\rho =\ell^ 2$$ and correspondingly within 50 % for $$\rho =\ell^ 1$$.
Reviewer: D.Yu.Grigorev

##### MSC:
 68Q25 Analysis of algorithms and problem complexity
Full Text: