On the complexity of some common geometric location problems. (English) Zbl 0534.68032

Megiddo, Nimrod; Supowit, Kenneth J.

SIAM J. Comput. 13, 182-196 (1984).

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

Keywords:

computational geometry; p-center problem; p-median problem; NP-hard