Randomized Rounding

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.

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">{{hint}}</p>
<div class="sets" id="sets"></div>
<div class="elems" id="elems"></div>
<div class="stats">
  <span>{{lp_label}}: <b id="lp">—</b></span>
  <span>{{round_label}}: <b id="round">—</b></span>
  <span>{{avg_label}} <b id="ntrials">0</b> {{trials_word}}: <b id="avg">—</b></span>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="once" type="button">{{btn_once}}</button>
  <button id="many" type="button">{{btn_many}}</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; }
.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; }

// Code not found

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.

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.

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.

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.