SIAM Journal on Computing · 1984 · 670 citations · 12 references
Natural SciencesComputer ScienceMathematicsDiscrete MathematicsGeometryOptimizationApproximation AlgorithmsGeometric OptimizationMetric GeometryP-center ProblemP-median ProblemPoint LocationApproximation Algorithms For P-medianDiscrete P-center ProblemDiscrete P-median ProblemExact Algorithms For P-medianMetrics
Given n demand points in the plane, the p-center problem is to find p supply points (anywhere in the plane) so as to minimize the maximum distance from a demand point to its respective nearest supply point. The p-median problem is to minimize the sum of distances from demand points to their respective nearest supply points. We prove that the p-center and the p-median problems relative to both the Euclidean and the rectilinear metrics are NP-hard. In fact, we prove that it is NP-hard even to approximate the p-center problems sufficiently closely. The reductions are from 3-satisfiability.
12