322. 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.

322.1. Formulation

s.t.:

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

322.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.

322.3. Solution methods

Decision-version of -center: “is there a placement with max distance ?” 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 .

1. Sort all distinct values
2. Binary search: for candidate , check if a feasible -coverage exists (set covering feasibility)
3. 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.

322.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 OPT. Tight — no better than 2 is possible unless P = NP.

322.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

322.6. See also

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