Introduction

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.

Place the Facilities

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">Dots are <b>clients</b>; squares are <b>candidate sites</b>. Click squares
to open up to <b id="pcap">p = 2</b> facilities. Each client connects to its nearest open
facility and the <b>total distance</b> updates. Checking a choice is instant — finding the
best one is NP-hard.</p>
<svg id="map" viewBox="0 0 320 240" width="100%"></svg>
<div class="status" id="status">Open facilities, then compare.</div>
<div class="btns">
  <button id="find" type="button">Find optimum</button>
  <button id="reset" type="button" class="ghost">Clear</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// p-median: open exactly p facilities (here p = 2) among the candidate SITES so the
// TOTAL distance from every client to its NEAREST open facility is minimized.
// Checking one choice = assign-to-nearest + sum (a quick scan). Finding the best
// choice in general is NP-hard (Kariv & Hakimi, 1979); here we brute force "n choose p".
const P = 2;
const CLIENTS = [
  [40,40],[80,60],[60,110],[35,170],[95,200],
  [180,50],[230,30],[270,90],[200,140],[160,200],
  [260,180],[300,150],[120,150],[210,210]
];
const SITES = [
  [60,70],[55,160],[110,120],[210,60],[255,110],[235,185],[150,180]
];
const open = new Set();          // indices of SITES the player opened

const dist = (a,b) => Math.hypot(a[0]-b[0], a[1]-b[1]);

// Total cost of a given set of open-site indices: each client to its nearest open site.
function cost(setIdx){
  if(setIdx.length === 0) return Infinity;
  let total = 0;
  for(const c of CLIENTS){
    let best = Infinity;
    for(const s of setIdx){ const d = dist(c, SITES[s]); if(d < best) best = d; }
    total += best;
  }
  return total;
}
// nearest open site index for a client (for drawing links)
function nearest(c, setIdx){
  let best = Infinity, bi = -1;
  for(const s of setIdx){ const d = dist(c, SITES[s]); if(d < best){ best = d; bi = s; } }
  return bi;
}

const svg = document.getElementById('map');
const NS = 'http://www.w3.org/2000/svg';
function el(tag, attrs){ const e = document.createElementNS(NS, tag);
  for(const k in attrs) e.setAttribute(k, attrs[k]); return e; }

function render(){
  svg.innerHTML = '';
  const setIdx = [...open];
  // links client -> nearest open facility
  if(setIdx.length){
    for(const c of CLIENTS){ const bi = nearest(c, setIdx);
      svg.appendChild(el('line', {x1:c[0], y1:c[1], x2:SITES[bi][0], y2:SITES[bi][1], class:'link'})); }
  }
  // candidate sites (squares)
  SITES.forEach((s,i)=>{
    const r = el('rect', {x:s[0]-7, y:s[1]-7, width:14, height:14, rx:3,
      class:'site'+(open.has(i)?' open':'')});
    r.addEventListener('click', ()=>{ toggle(i); });
    svg.appendChild(r);
  });
  // clients (dots) drawn on top
  for(const c of CLIENTS) svg.appendChild(el('circle', {cx:c[0], cy:c[1], r:4, class:'client'}));
}

function toggle(i){
  if(open.has(i)) open.delete(i);
  else { if(open.size >= P) return setStatus(fmt('You may open at most p = %P% facilities. Clear one first.', { P: P }),'bad'); open.add(i); }
  render(); report();
}
function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status '+cls; }
function report(){
  if(open.size < P){ setStatus(fmt('Open %v% more facilit%v2%.', { v: P-open.size, v2: P-open.size>1?'ies':'y' }),''); return; }
  const c = cost([...open]);
  setStatus(fmt('Total distance = %c%. Can you do better?', { c: c.toFixed(1) }),'');
}

// Brute force: try every choice of P sites out of SITES.length, keep the cheapest.
function find(){
  const n = SITES.length; let best = Infinity, bestSet = null, tried = 0;
  const idx = [];
  (function choose(start, k){
    if(k === 0){ tried++; const c = cost(idx); if(c < best){ best = c; bestSet = idx.slice(); } return; }
    for(let i = start; i <= n - k; i++){ idx.push(i); choose(i+1, k-1); idx.pop(); }
  })(0, P);
  open.clear(); bestSet.forEach(i => open.add(i)); render();
  setStatus(fmt('Optimum after checking all %tried% choices: total distance = %best%.', { tried: tried, best: best.toFixed(1) }),'ok');
  console.log('Optimal sites:', bestSet.join(','), '| total =', best.toFixed(2), '| combinations tried =', tried);
}
document.getElementById('pcap').textContent = 'p = '+P;
document.getElementById('find').addEventListener('click', find);
document.getElementById('reset').addEventListener('click', ()=>{ open.clear(); render(); report(); });
render(); report();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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

Conclusion

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.

Share this article

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

Comments

Loading comments...

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