Facility Location (p-median)

Suppose you run a delivery company with customers scattered across a city, and the budget for exactly p warehouses. Every customer will be served by the nearest warehouse. Where do you build them so that the total distance everyone travels is as small as possible?

That is the p-median problem, one of the founding questions of facility location. Its twin, the p-center problem, instead minimizes the worst-case distance — no client should ever be too far from a facility. Hospitals, fire stations, cell towers, cloud servers and retail stores all live on this same map.

The question is easy to state and easy to check: given a set of locations, anyone can add up the distances. But finding the best p spots out of all the possibilities is one of the genuinely hard problems of computer science — and that gap is what this article is about.

Here is a map of clients (dots) and candidate sites (squares) where you may open facilities. Choose p of the candidate sites: each client is assigned to its nearest open facility, and the lines and total distance update instantly.

<p class="hint">{{hint}}</p>
<svg id="map" viewBox="0 0 320 240" width="100%"></svg>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="find" type="button">{{btn_find}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#map { background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 10px; display: block; max-width: 480px; }
.client { fill: #1d3557; }
.link { stroke: #8aa0b4; stroke-width: 1.4; }
.site { fill: #c9ccd1; stroke: #adb1b8; cursor: pointer; transition: all .12s; }
.site:hover { fill: #bcc0c6; }
.site.open { fill: #e63946; stroke: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Try to beat the computer. Checking any choice is effortless — assign each client to its closest facility and add up the distances. Finding the best set of p sites is the hard part: press Find optimum and the computer simply tries every way to choose p of the candidates. With a handful of sites that's manageable, but the number of combinations explodes as the map grows.

How hard is it to place facilities optimally? Not the checking — the finding.

• Checking a candidate solution is trivial: assign each client to its nearest open facility and sum the distances. Easy.
• Brute force tries every way to pick p sites out of n candidates — that's "n choose p" combinations, which blows up fast.
• It's NP-hard. In 1979, Oded Kariv and S. Louis Hakimi proved that both the p-median and the p-center problems are NP-hard, even on networks. The classic reduction comes from dominating set: deciding whether p facilities can cover everyone within a fixed radius is exactly the NP-complete dominating-set question in disguise.
• So there is no known fast algorithm that always returns the optimal layout, and unless P vs NP is resolved in P's favor, there never will be.

The good news: facility location is approximable. Clever algorithms (local search, LP rounding, primal-dual methods) get provably within a small constant factor of the optimum, and solvers handle real instances every day. But the exact optimum, guaranteed, in reasonable time on a large map? That is intractability hiding behind a friendly pin on a map.

"Pick a few good locations so nothing is far away" is one of the most common shapes a real decision can take, and the p-median model is its clean form:

• Logistics and supply chains: where to build warehouses, distribution centers and depots to cut transport cost.
• Public services: siting hospitals, schools, fire stations and polling places so coverage stays fair — often the p-center variant, which bounds the worst travel time.
• Networks: placing cell towers, content-delivery caches and cloud servers close to demand.
• Machine learning: the famous k-means clustering algorithm is the continuous cousin of p-median — choose k centers to minimize the total distance from points to their nearest center.

Understand why facility location is hard and you've met a whole family of optimization problems, close relatives of set cover and the vertex cover problems that share the same NP-hard heart.

Facility location hides a quiet lesson: a question a child could ask — "where should we put our p shops?" — is, in full generality, NP-hard. Kariv and Hakimi pinned that down in 1979, and the dominating-set reduction shows it is no accident.

So when your delivery app, your phone network or your favorite clustering tool gives you an answer that's good but maybe not perfect, that's not laziness — it's the honest response to a problem where the perfect answer is, as far as we know, computationally out of reach. It's P vs NP hiding behind a map full of pins, and we navigate it every single day.