Introduction

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.

Place the Hospitals

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">The dots are towns. Click <b>two</b> to build hospitals there — each town is served by its nearest hospital. The dashed line marks the <span class="r">worst-served</span> town; shrink that distance, then Optimize.</p>
<svg id="map" viewBox="0 0 320 230" class="map"></svg>
<div class="meter">
  <div>Hospitals: <b id="k">0</b> / 2</div>
  <div>Worst distance: <b id="worst" class="r">—</b></div>
  <div id="msg" class="msg"></div>
</div>
<div class="btns">
  <button id="opt" type="button">Optimize</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Vertex k-center: choose k town sites for facilities to minimize the largest distance from any town to its nearest facility. NP-hard; the farthest-first greedy is a 2-approximation. Here we brute-force k=2.
const K = 2;
// towns: a left cluster plus two far-apart outliers -> placement matters
const TOWNS = [
  { x: 50, y: 60 }, { x: 70, y: 90 }, { x: 60, y: 120 }, { x: 90, y: 70 },
  { x: 80, y: 140 }, { x: 250, y: 50 }, { x: 270, y: 110 }, { x: 240, y: 170 }, { x: 150, y: 190 }
];
const N = TOWNS.length;
let fac = []; // indices of chosen facility towns

function dist(a, b) { return Math.hypot(TOWNS[a].x - TOWNS[b].x, TOWNS[a].y - TOWNS[b].y); }

// returns {worst: distance, town: index, nearest: facilityIndex}
function evaluate(facs) {
  if (!facs.length) return { worst: Infinity, town: -1, nearest: -1 };
  let worst = -1, wt = -1, wn = -1;
  for (let t = 0; t < N; t++) {
    let best = Infinity, bf = -1;
    for (const f of facs) { const d = dist(t, f); if (d < best) { best = d; bf = f; } }
    if (best > worst) { worst = best; wt = t; wn = bf; }
  }
  return { worst, town: wt, nearest: wn };
}

function toggle(i) {
  const k = fac.indexOf(i);
  if (k >= 0) fac.splice(k, 1);
  else { if (fac.length >= K) fac.shift(); fac.push(i); }
  render();
}

function render() {
  const ev = evaluate(fac);
  const svg = ['<svg/>'];
  let s = '';
  // worst link
  if (fac.length && ev.town >= 0) {
    s += '<line class="link" x1="' + TOWNS[ev.town].x + '" y1="' + TOWNS[ev.town].y +
      '" x2="' + TOWNS[ev.nearest].x + '" y2="' + TOWNS[ev.nearest].y + '" />';
  }
  TOWNS.forEach((t, i) => {
    const isFac = fac.includes(i);
    if (isFac) s += '<rect class="fac" x="' + (t.x - 7) + '" y="' + (t.y - 7) + '" width="14" height="14" rx="3" data-i="' + i + '"/>';
    else { const cls = (i === ev.town && fac.length) ? 'town worst' : 'town'; s += '<circle class="' + cls + '" cx="' + t.x + '" cy="' + t.y + '" r="7" data-i="' + i + '"/>'; }
  });
  document.getElementById('map').innerHTML = s;
  document.getElementById('map').querySelectorAll('[data-i]').forEach(el =>
    el.addEventListener('click', () => toggle(+el.dataset.i)));
  document.getElementById('k').textContent = fac.length;
  document.getElementById('worst').textContent = fac.length ? Math.round(ev.worst) : '—';
  const msg = document.getElementById('msg');
  if (fac.length < K) { msg.style.color = '#777'; msg.textContent = fmt('Place %v% more.', { v: K - fac.length }); }
  else if (Math.round(ev.worst) <= OPT + 1) { msg.style.color = '#0a7d33'; msg.textContent = fmt('✓ Optimal placement! (worst ≈ %OPT%)', { OPT: OPT }); }
  else { msg.style.color = '#b9770e'; msg.textContent = fmt('Optimal worst distance is %OPT% — keep trying.', { OPT: OPT }); }
}

function optimize() {
  let best = null, bestW = Infinity;
  for (let i = 0; i < N; i++) for (let j = i + 1; j < N; j++) {
    const w = evaluate([i, j]).worst; if (w < bestW) { bestW = w; best = [i, j]; }
  }
  fac = best; render();
}

// precompute the optimum worst-distance for the success message
let OPT = Infinity;
for (let i = 0; i < N; i++) for (let j = i + 1; j < N; j++) OPT = Math.min(OPT, evaluate([i, j]).worst);
OPT = Math.round(OPT);

document.getElementById('opt').addEventListener('click', optimize);
document.getElementById('reset').addEventListener('click', () => { fac = []; render(); });
render();
Result
Console

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.

The Hard Part

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/facility-location/Content licensed under CC BY-NC 4.0.