Introduction

Suppose you must decide, for each of a dozen warehouses, whether to open it or not — a clean yes/no choice — so that every customer is served at the lowest total cost. This is an integer problem, and in general it is NP-hard: there is no known fast algorithm that always finds the cheapest set.

But there is a famous trick. Relax the requirement that every decision be 0 or 1, and instead allow fractions: "open 0.4 of this warehouse." Now the problem becomes a linear program (LP), which we can solve quickly and optimally. The catch: you can't open four-tenths of a building. The LP's answer is a beautiful number that you cannot actually use.

Randomized rounding is how we cash it in. Treat each fraction as a probability and flip a biased coin: a variable set to 0.4 becomes "open" with 40% chance. It sounds reckless — yet the expected cost lands exactly on the LP's, and with a little care the result is provably close to the true optimum. Chance, used deliberately, turns an impossible answer into a usable one.

Round the Fractions

Below is a small set-cover problem: a handful of sets, each with a cost, that together must cover every element. The panel first shows the LP relaxation — the optimal fractional answer, where a set can be chosen "partially." That fractional cost is a lower bound on any real solution.

<p class="hint">A small <b>set-cover</b> problem: pick sets so every element (1–6) is covered, as cheaply as possible. The LP relaxation lets a set be chosen <i>fractionally</i>. Randomized rounding turns each fraction into a yes/no choice by flipping a biased coin — and the average cost stays near the LP value.</p>
<div class="sets" id="sets"></div>
<div class="elems" id="elems"></div>
<div class="stats">
  <span>LP (fractional) cost: <b id="lp">—</b></span>
  <span>This round: <b id="round">—</b></span>
  <span>Avg over <b id="ntrials">0</b> trials: <b id="avg">—</b></span>
</div>
<div class="status" id="status">Press "Round once" to flip the coins.</div>
<div class="btns">
  <button id="once" type="button">Round once</button>
  <button id="many" type="button">Run 200 trials</button>
  <button id="reset" type="button" class="ghost">Reset stats</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; }
.sets { display: grid; grid-template-columns: repeat(4, 1fr); gap: 6px; margin: .4rem 0; }
.set { border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem; background: #f4f7fa;
       text-align: center; transition: all .12s; }
.set .name { font-weight: 700; color: #1d3557; }
.set .info { font-size: .78rem; color: #555; margin-top: .15rem; }
.set.on { background: #1d3557; border-color: #142844; color: #fff; }
.set.on .name, .set.on .info { color: #fff; }
.elems { display: flex; gap: 5px; flex-wrap: wrap; margin: .5rem 0; }
.el { width: 34px; height: 34px; display: flex; align-items: center; justify-content: center;
      border-radius: 50%; font-weight: 700; font-size: .9rem; background: #e8eef3;
      color: #1d3557; border: 1px solid #cdd9e3; }
.el.covered { background: #0a7d33; border-color: #086628; color: #fff; }
.el.missing { background: #e63946; border-color: #c92f3c; color: #fff; }
.stats { display: flex; flex-direction: column; gap: .2rem; font-size: .9rem; margin: .5rem 0; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 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 i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Randomized rounding for SET COVER ──────────────────────────────────────
// Elements 1..6 must each be covered. Each set covers some elements and has a
// cost. The LP relaxation allows a fractional amount x_S in [0,1] of each set,
// requiring that for every element the x_S over sets containing it sum to >= 1.
// We hard-code an LP-optimal fractional solution for this instance.
// Randomized rounding: include set S independently with probability x_S.
const ELEMS = [1,2,3,4,5,6];
const SETS = [
  { name: 'A', cost: 3, cover: [1,2,3], x: 0.5 },
  { name: 'B', cost: 3, cover: [4,5,6], x: 0.5 },
  { name: 'C', cost: 2, cover: [1,4],   x: 0.5 },
  { name: 'D', cost: 2, cover: [2,5],   x: 0.5 },
  { name: 'E', cost: 2, cover: [3,6],   x: 0.5 },
];
// LP cost = sum cost_S * x_S
const LP = SETS.reduce((s, S) => s + S.cost * S.x, 0); // = 6.0

let sumCost = 0, nFeasible = 0, lastChosen = [];

function fmt(x){ return (Math.round(x*100)/100).toFixed(2); }

function renderSets(chosen){
  const c = document.getElementById('sets'); c.innerHTML = '';
  SETS.forEach((S, i) => {
    const d = document.createElement('div');
    const on = chosen && chosen[i];
    d.className = 'set' + (on ? ' on' : '');
    d.innerHTML = '<div class="name">'+S.name+'</div>' +
      '<div class="info">cost '+S.cost+' · x='+S.x+'<br>{'+S.cover.join(',')+'}</div>';
    c.appendChild(d);
  });
}
function renderElems(covered){
  const c = document.getElementById('elems'); c.innerHTML = '';
  ELEMS.forEach(e => {
    const d = document.createElement('div');
    let cls = 'el';
    if (covered) cls += covered.has(e) ? ' covered' : ' missing';
    d.className = cls; d.textContent = e; c.appendChild(d);
  });
}
function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls||''); }

// One randomized-rounding draw: include set i with probability x_i.
function roundOnce(){
  const chosen = SETS.map(S => Math.random() < S.x);
  const covered = new Set();
  SETS.forEach((S, i) => { if (chosen[i]) S.cover.forEach(e => covered.add(e)); });
  const cost = SETS.reduce((s, S, i) => s + (chosen[i] ? S.cost : 0), 0);
  const feasible = ELEMS.every(e => covered.has(e));
  return { chosen, covered, cost, feasible };
}

function showRound(r){
  renderSets(r.chosen); renderElems(r.covered);
  document.getElementById('round').textContent = fmt(r.cost);
  if (r.feasible) setStatus(i18nFmt('Feasible! Cost %fmt% (LP lower bound is %fmt2%).', { fmt: fmt(r.cost), fmt2: fmt(LP) }), 'ok');
  else setStatus('Some element uncovered — in practice we re-flip until feasible.', 'bad');
}
function recordFeasible(cost){ sumCost += cost; nFeasible++; updateAvg(); }
function updateAvg(){
  document.getElementById('ntrials').textContent = nFeasible;
  document.getElementById('avg').textContent = nFeasible ? fmt(sumCost / nFeasible) : '—';
}

function once(){
  // Keep flipping until we get a feasible cover, then show & record it.
  let r, guard = 0;
  do { r = roundOnce(); guard++; } while (!r.feasible && guard < 1000);
  showRound(r);
  if (r.feasible) recordFeasible(r.cost);
}
function many(){
  let added = 0;
  for (let t = 0; t < 200; t++){
    let r, guard = 0;
    do { r = roundOnce(); guard++; } while (!r.feasible && guard < 1000);
    if (r.feasible) { recordFeasible(r.cost); added++; }
  }
  const r = roundOnce(); showRound(r);
  setStatus(i18nFmt('Ran 200 feasible trials. Average rounded cost = %fmt%, just above the LP value %fmt2%.', { fmt: fmt(sumCost/nFeasible), fmt2: fmt(LP) }), 'ok');
  console.log('LP =', fmt(LP), '| feasible trials =', nFeasible, '| avg cost =', fmt(sumCost/nFeasible));
}

document.getElementById('lp').textContent = fmt(LP);
document.getElementById('once').addEventListener('click', once);
document.getElementById('many').addEventListener('click', many);
document.getElementById('reset').addEventListener('click', () => {
  sumCost = 0; nFeasible = 0; updateAvg();
  renderSets(null); renderElems(null);
  setStatus('Press "Round once" to flip the coins.', '');
});
renderSets(null); renderElems(null);
Result
Console

Press Round once to flip a biased coin for each set: a set with LP value 0.6 is taken with 60% probability. The rounded solution is a genuine yes/no plan — sometimes a little cheaper than expected, sometimes a little dearer, occasionally missing an element so the round is repeated. Press Run 200 trials and watch the average rounded cost settle just above the LP value, exactly as the theory predicts. The fractions were never the answer; they were the recipe for a good random one.

The Real Complexity

Randomized rounding is not a heuristic that "usually works" — it is a proven design technique, introduced by Prabhakar Raghavan and Clark Thompson in 1987. Its power rests on two ideas.

  • Linearity of expectation. If the LP sets a variable to value p, round it to 1 with probability p. Then the expected cost of the rounded solution equals the LP's cost — and because the LP is a relaxation, that cost is at most the unknown integer optimum. The average rounded answer is automatically as good as the best possible one.
  • Concentration. A single random draw could be unlucky, but Chernoff-style bounds show the outcome is tightly clustered around its mean. Repeat a few times and take the cheapest feasible result, and you obtain a solution provably within a small factor of optimal — for set cover, that factor is about ln n.
  • It runs in polynomial time. Solving the LP is fast, and the rounding is one coin flip per variable, so the whole method is efficient — a polynomial-time approximation algorithm for problems whose exact versions are NP-hard.

The deep point: the hardness of the integer problem hasn't vanished. We still can't find the exact optimum quickly. What randomized rounding buys is a guarantee on how close we get — turning intractability into a controlled, quantified gap rather than a wall.

Where It Matters

Whenever a real decision is discrete but its relaxed version is a tractable LP, randomized rounding is in the toolbox:

  • Network routing. The technique was born routing wires on chips and packets through networks — split a fractional flow into actual paths while keeping congestion low.
  • Facility location and clustering. Deciding which data centers, warehouses or cell towers to open is a classic LP-relax-and-round problem.
  • Scheduling and resource allocation. Assigning jobs to machines or ad slots to advertisers becomes a covering or packing LP, then rounded.
  • Approximation algorithms broadly. It is one of the standard ways to attack any set cover or covering-and-packing problem with a provable ratio.

Learn randomized rounding and you've learned the central bridge of modern algorithm design: solve the easy continuous version, then gamble responsibly back to the discrete world.

Conclusion

Randomized rounding captures one of the most elegant moves in computer science: when the honest yes/no problem is too hard, solve a softer fractional version you can handle, then let a carefully biased coin translate the fractions back into decisions. Linearity of expectation guarantees the average is as good as the best possible plan; concentration keeps any single run close.

So a number like 0.4 is not a failure of the method — it is a probability, an instruction for a coin. The next time an optimizer hands you an answer you can't literally act on, remember Raghavan and Thompson: the path from the impossible fraction to a provably good decision can be a single, well-weighted flip. For the line between easy and hard that all of this dances around, see P vs NP.

Share this article

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

Comments

Loading comments...

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