Raghavan-Thompson Randomized Rounding

Purpose: Turn a fractional LP solution into an integral one by treating the fractional values as probabilities — the technique that made linear programming a general-purpose tool for approximation algorithms (1987).

The Recipe

1. Formulate the problem as an integer linear program.
2. Relax the integrality constraints ($x_i\in \{0,1\}\to x_i\in [0,1]$) and solve the LP in polynomial time. Its value $\mathrm{LP}$ bounds $\mathrm{OPT}$.
3. Round randomly: set $x_i=1$ independently with probability $x_i^{\ast }$.
4. Analyse: the expected objective is exactly $\mathrm{LP}$ by linearity, and concentration bounds (Chernoff) show the constraints are nearly satisfied with high probability.
5. Repair or repeat to fix the few violated constraints.

Worked example: set cover

$\min {\sum }_S{c}_S{x}_S\text{subject to}{\sum }_{S\ni e}{x}_S\ge 1\forall e,x_S\in \{0,1\}.$

Solve the LP, then round: repeat $O(\log n)$ independent rounds, in each of which set $S$ is picked with probability $x_S^{\ast }$.

• Cost. Each round costs $\mathrm{LP}$ in expectation, so $O(\log n)\cdot \mathrm{LP}$ total.
• Coverage. Element $e$ is missed in one round with probability ${\prod }_{S\ni e}(1-x_S^{\ast })\le e^{-\sum x_S^{\ast }}\le e^{-1}$. After $O(\log n)$ rounds the failure probability is $1/\mathrm{poly}(n)$; union bound over all elements.

Result: an $O(\log n)$-approximation — matching the greedy algorithm, and matching the $\Omega (\ln n)$ hardness (Feige/Dinur-Steurer).

The key tool: Chernoff bounds

For independent $X_i\in [0,1]$ with $\mu =\mathbb{E}[\sum X_i]$:

$\mathrm{Pr}\left[\sum X_i\ge (1+\delta )\mu \right]\le \exp \left(-\frac{{\delta }^2\mu }{2+\delta }\right),$
$\mathrm{Pr}\left[\sum X_i\le (1-\delta )\mu \right]\le \exp \left(-\frac{{\delta }^2\mu }{2}\right).$

These say a sum of independent bounded variables is very close to its mean — which is exactly the guarantee randomized rounding needs to claim “the rounded solution nearly satisfies every constraint.”

Where it applies

Problem	LP relaxation	Result
Set cover	fractional cover	$O(\log n)$-approximation
Vertex cover	fractional cover (half-integral)	2-approximation (deterministic rounding at $1/2$)
Congestion minimisation / multicommodity routing	fractional flow	$O(\log n/\log \log n)$ congestion — the original application
Facility location	fractional assignment	constant factor with clustered rounding
Scheduling on unrelated machines	assignment LP	2-approximation (Lenstra-Shmoys-Tardos)
MAX-SAT	LP + biased coins	3/4-approximation

The original Raghavan-Thompson paper was about global wire routing in VLSI: route many nets through a grid minimising the maximum congestion. Fractional routing is a flow LP; rounding each net to a single random path with the LP’s probabilities keeps congestion within $O(\log n/\log \log n)$ of optimal.

Derandomisation

Randomized rounding can be made deterministic by the method of conditional expectations: decide the variables one at a time, always choosing the value that keeps the conditional expectation of the objective at least as good. Pessimistic estimators make the conditional expectations efficiently computable. This is a genuinely useful proof technique and occasionally a constructive one.

Variants / Use Cases

• Goemans-Williamson — the SDP analogue, with hyperplane rounding
• Approximation Algorithms — the topic page
• Randomized Algorithms — Chernoff bounds and concentration
• In a contest — LP relaxations rarely appear directly, but the idea that a fractional optimum bounds the integral one is a useful way to reason about greedy quality