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


68Q25 Analysis of algorithms and problem complexity
Full Text: DOI