Where to Build the Hospital?

A region needs new hospitals, but the budget covers only a few. Where do you build them so that nobody — not even the most remote village — is too far from care?

The lazy answer is to plant one in the biggest city. But that abandons everyone else: the farthest family might still be a three-hour drive from an emergency room. Good placement isn't about serving the most people; it's about making sure the worst-off person is as close as possible.

That's the facility location problem — and in the version that minimizes the worst distance, the k-center problem. It's a cousin of set cover and vertex cover: you're covering a population with a limited number of well-placed points. And like them, it looks like common sense and turns out to be NP-hard.

Try it. The dots are towns. Click two of them to build hospitals there; every town is then served by its nearest hospital. The demo highlights the worst-served town and the distance it must travel — the number you're trying to minimize.

<p class="hint">{{hint}}</p>
<svg id="map" viewBox="0 0 320 230" class="map"></svg>
<div class="meter">
  <div>{{hospitals_label}}: <b id="k">0</b> / 2</div>
  <div>{{worst_dist_label}}: <b id="worst" class="r">—</b></div>
  <div id="msg" class="msg"></div>
</div>
<div class="btns">
  <button id="opt" type="button">{{btn_optimize}}</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; }
.hint .r { color: #c0392b; font-weight: 700; }
.map { width: 100%; max-width: 460px; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; }
.town { fill: #8aa0b3; cursor: pointer; transition: fill .12s; }
.town:hover { fill: #457b9d; }
.fac { fill: #2a9d8f; stroke: #fff; stroke-width: 2; cursor: pointer; }
.worst { fill: #c0392b; }
.lbl { font: 600 9px ui-monospace, monospace; fill: #6a7b88; pointer-events: none; }
.link { stroke: #c0392b; stroke-width: 2; stroke-dasharray: 4 3; }
.meter { display: flex; gap: 1.3rem; align-items: center; font-size: 1rem; margin: .8rem 0 .6rem; flex-wrap: wrap; }
.meter .r { color: #c0392b; }
.msg { font-weight: 700; color: #0a7d33; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

Move your two hospitals around to shrink that worst distance, then hit Optimize for the best possible pair. Notice how the obvious "cover the cluster" choice can leave a lone town stranded — minimizing the maximum distance is a different, trickier goal than serving the crowd.

Here's the shape of the difficulty:

• Checking a placement is easy: for each town find its nearest facility, take the largest of those distances.
• Brute force means trying every way to choose k sites from n candidates — C(n, k), which explodes.
• It's NP-hard. Both k-center (minimize the worst distance) and k-median (minimize total distance) are NP-hard, related to set/vertex cover.
• But it approximates beautifully. A simple farthest-first greedy — repeatedly open a facility at the town currently worst-served — gives a 2-approximation for k-center: never more than twice the optimal worst-distance. Remarkably, doing better than 2 is itself NP-hard, so the simple method is essentially the best possible.
• Practice adds capacities, costs and demand, then leans on integer programming and these approximation guarantees.

It's a happy middle ground: provably hard to solve exactly, yet a one-line greedy gets you provably close.

Wherever placement decides who gets served and how fast, this problem is at work:

• Healthcare and public services: hospitals, clinics, schools and fire stations placed for equitable access.
• Emergency response: ambulance and fire-station siting to minimize the worst response time.
• Logistics and retail: warehouses, distribution centers and stores balancing delivery distance and cost.
• Telecom and computing: cell towers, Wi-Fi access points and CDN servers placed near demand.
• Equity: because k-center targets the worst-off, it's a natural fit for fairness in public planning.

The objective you choose — worst distance, total distance, or cost — changes the answer, which is why facility location is a rich family of problems, not just one.

Facility location is decision-making with a conscience. The math cares about the person farthest from help, and getting it exactly right is NP-hard — too hard to brute-force for a real map.

But this is one of the cheerful hard problems: a humble farthest-first greedy comes with a proof that it's within a factor of two of optimal, and that you can't reliably do better. It's a reminder that "NP-hard" is rarely the end of the story — often it's the start of a clever approximation that's good enough to plan a hospital, a warehouse, or a network by.