p-Center

325. p-Center

$𝑝$ -Center Problem: place $𝑝$ facilities to minimize the maximum distance any customer must travel to its nearest facility. A minimax objective — focuses on the worst-served customer, not average.

325.1. Formulation

min_{𝑦, 𝑥, 𝑧} 𝑧

s.t.:

𝑧 \geq \sum_{𝑗} 𝑐_{𝑖 𝑗} 𝑥_{𝑖 𝑗}, \forall 𝑖 (z bounds max assigned distance)

\sum_{𝑗} 𝑥_{𝑖 𝑗} = 1, \forall 𝑖

𝑥_{𝑖 𝑗} \leq 𝑦_{𝑗}, \sum_{𝑗} 𝑦_{𝑗} = 𝑝, 𝑦_{𝑗} \in {0, 1}

Variable $𝑧$ is the maximum cost; minimizing $𝑧$ subject to constraints is minimax.

325.2. Why minimax matters

Emergency services: response time to the worst-located resident matters more than average
Equity: avoid concentrating service in dense areas at the expense of remote customers
Service-level agreements: “no customer more than $𝑋$ miles away” is a hard constraint

vs $𝑝$ -median ( $𝑝$ -median) which minimizes total (= average × N) distance.

325.3. Solution methods

Decision-version of $𝑝$ -center: “is there a placement with max distance $\leq 𝑟$ ?” This is a set covering problem: each facility covers all customers within $𝑟$ , and you need $𝑝$ facilities whose covers union to the full customer set.

Algorithm: binary search on $𝑟$ .

Sort all distinct $𝑐_{𝑖 𝑗}$ values
Binary search: for candidate $𝑟$ , check if a feasible $𝑝$ -coverage exists (set covering feasibility)
The smallest feasible $𝑟$ is the optimum

Set covering itself is NP-hard, so this gives an NP-hard subroutine — but the binary search keeps the number of feasibility checks small.

325.4. Approximation

For metric $𝑝$ -center (triangle inequality), 2-approximation is achievable (Hochbaum-Shmoys 1985): greedy farthest-first.

Choose first facility: any node
Repeat p-1 times:
    Choose the unselected node FARTHEST from all already-selected facilities

This achieves max distance $\leq 2 \cdot$ OPT. Tight — no better than 2 is possible unless P = NP.

325.5. Applications

Fire / ambulance station placement — minimize worst-case response time
Distribution center location under SLA — “all customers within 200 miles”
Schools — equitable access (no child more than $𝑋$ miles)
Cellular networks with coverage radius

325.6. See also

$𝑝$ -median — total-distance variant
Set Covering — the feasibility subproblem
Facility Location overview