pcenter

The p-center problem, sometimes written as p-center, is a classic optimization problem in operations research and computer science. Given a set of demand points and a metric that defines distances between points, the goal is to place p facilities so that the maximum distance from any demand point to its nearest facility is minimized. The objective is to achieve the smallest possible service radius that covers all demand points with at most p facilities.

There are two common versions of the problem. In the discrete p-center problem, facilities may be located only at a specified set of candidate sites. In the continuous p-center problem, facilities may be placed anywhere in the space, subject to the chosen distance metric (for example, Euclidean, Manhattan, or graph distance). The problem is widely studied in both geometric and graph‑based settings.

Mathematically, let D be the set of demand points, S the set of candidate facility sites, and dist(i, j) the distance between demand point i and candidate site j. The aim is to select at most p sites from S to minimize R, such that every i in D is within distance R of at least one selected site. This is typically formulated with binary variables indicating site selection and assignment, along with a constraint on the number of facilities and distance bounds.

Complexity and methods: The p-center problem is NP-hard in general, with the decision version NP-complete. Exact solutions often rely on integer programming or branch-and-bound approaches. Practical solutions frequently employ 2-approximation algorithms for certain graph and geometric cases, plus various heuristics and metaheuristics to handle large instances.

Applications include emergency services planning, facility location for distribution and telecommunications, urban planning, and disaster response, where minimizing the worst-case service distance is crucial. Related problems include the p-median problem and the k-center problem.