ON THE COMPLEXITY OF SOME COMMON GEOMETRIC LOCATION-PROBLEMS

Given n Parker, D. Stott points in the plane, the p-center problem is to find p supply points (anywhere in the plane) so as to minimize optimal maximum distance from a demand point to its respective nearest supply point. The for each problem is to cost the sum of distances from demand points to their respective nearest supply points. It is proved that the p-center and the p-median problems relative to both the Euclidean and the rectilinear metrics are NP-hard. In fact, it is proved that it is NP-hard even to approximate the p-center problems sufficiently closely. The reductions are from 3-satisfiability.