Randomized Rounding¶

Map a tractable fractional or convex relaxation into a distribution over discrete candidates whose marginals, correlations, and geometry retain enough of the relaxation to prove feasibility and approximation quality probabilistically.

Version: v2 · 2026-09-06 · History
Domain-specific #: 2622
Origin domain: theoretical computer science
Subdomain: approximation algorithms and combinatorial optimization

Core Idea¶

Randomized rounding is an approximation-algorithm technique that converts a solution of a tractable continuous or fractional relaxation into a discrete candidate by sampling from a distribution designed from that relaxation. The relaxation supplies more than a lower or upper bound: its coordinates, vectors, or decomposition determine selection probabilities and correlations. The analysis then proves that the sampled discrete object is feasible, can be made feasible, and has objective value close to the relaxation bound with a specified probability or in expectation. Because the relaxation bounds the unknown discrete optimum, that comparison becomes an approximation guarantee.^[1]^[2]

The canonical 0–1 form begins with a fractional point \(x^*\in[0,1]^n\). Independent rounding sets \(X_i=1\) with probability \(x_i^*\) and zero otherwise, giving \(\mathbb E[X_i]=x_i^*\). For a linear objective, linearity of expectation yields \(\mathbb E[c^T X]=c^T x^*\). That identity is powerful but incomplete: independently chosen variables may violate covering, packing, cardinality, assignment, or connectivity constraints. A valid design therefore joins the probability map to a constraint analysis—often using Markov or Chernoff bounds, a union bound, negative correlation, rescaling, repetition, alteration, or repair.

The mature identity is broader than independent Bernoulli trials. Probabilities may be scaled or transformed; variables may be rounded dependently to preserve degrees or budgets; an LP flow may be decomposed into paths and one path sampled per demand; a semidefinite solution may be rounded by a random hyperplane. Goemans and Williamson's MAX CUT algorithm, for example, samples a random direction and separates relaxation vectors by the signs of their inner products with that direction.^[3] Across these variants, the invariant is a relaxation-parameterized distribution over integral candidates with a proved relation between relaxation structure and discrete performance.

Randomized rounding is both algorithmic and proof-theoretic. If a good discrete outcome has positive probability, then such an outcome exists, which can bound an integrality gap. If success probability is efficiently amplifiable, repeated sampling gives a randomized algorithm. If conditional expectations or pessimistic estimators can be computed, the random choices can often be fixed deterministically without worsening the guarantee.^[4]^[5] These are three uses of the same construction, not three definitions.

Structural Signature¶

Locked operation: discrete optimization instance + tractable relaxation and bound + relaxation-derived randomized map + joint objective/constraint analysis + success extraction -> integral feasible solution with a proved approximation guarantee, or a proved integrality-gap/existence bound.

The following roles are jointly diagnostic:

The discrete target. The desired output belongs to a combinatorial family such as a set cover, cut, assignment, route set, schedule, matching, or 0–1 vector. Its feasibility and objective are explicitly defined.
The tractable relaxation. Integrality, rank, or another hard discrete restriction is weakened to obtain an LP, SDP, convex program, fractional flow, or comparable surrogate that can be optimized or approximately solved efficiently.
The certified relaxation value. For minimization, the relaxation generally provides a lower bound on the integral optimum; for maximization, an upper bound. The rounding guarantee must state the direction of this comparison.
The parameterized probability map. The relaxation solution determines a distribution over discrete choices. This may use coordinate marginals \(\Pr[X_i=1]=x_i\), transformed probabilities \(f(x_i)\), sampled paths, random thresholds, hyperplanes, permutations, or correlated exchanges.
The preservation commitments. The scheme declares what it retains in expectation or almost surely: coordinate marginals, total cost, degree sums, cardinality, pairwise separation probabilities, or another statistic that connects the relaxation to the discrete target.
The bad events. Constraint violations and unacceptable objective loss are identified explicitly. A proof about expectation alone is not a feasibility proof.
The probability analysis. Tail inequalities, union bounds, correlation inequalities, local lemmas, geometric probability, or conditional expectations connect the designed distribution to the performance event.
The success extractor. The algorithm may accept a successful draw, repeat until success, alter or repair a draw, use a backup, or deterministically fix choices. Runtime and approximation claims include this step.
The approximation statement. The final guarantee specifies whether it holds in expectation, with constant probability, with high probability, or deterministically after derandomization, and compares a feasible integral result to the true optimum through the relaxation bound.

The simplest recognition test is therefore not “does the algorithm flip coins?” It is: does a tractable relaxation parameterize the random discrete construction, and does the analysis use that coupling to prove a bounded integral outcome?

What It Is Not¶

Not arbitrary randomized search. Random restarts, simulated annealing, and Monte Carlo exploration may sample candidates without deriving their distribution from a relaxation solution. They are randomized algorithms, but not randomized rounding on that basis.
Not numerical stochastic rounding. In floating-point arithmetic, stochastic rounding maps a scalar to adjacent machine values with probabilities chosen to preserve its expectation. It shares a marginal-preservation pattern, but it need not start from a combinatorial relaxation, prove feasibility, or approximate an optimization optimum. It is a neighboring numerical method, not an exact alias.
Not deterministic threshold rounding. Setting \(X_i=1\) whenever \(x_i\ge 1/2\) uses a relaxation but no randomized map. It may be a rounding algorithm, not randomized rounding.
Not the probabilistic method by itself. The probabilistic method proves existence by defining a random object. Randomized rounding is more specific: the distribution depends on a relaxation solution for the particular instance and is normally designed for an efficient construction or an instance-sensitive gap bound.
Not relaxation alone. Solving an LP or SDP produces a bound and a fractional object. Until a rounding map and performance analysis connect that object to an integral candidate, randomized rounding has not occurred.
Not guaranteed per-draw feasibility. Some schemes preserve feasibility in every outcome; many independent schemes do not. Feasibility may arise only with positive probability, after alteration, or after a correlated design. Calling the raw sample “the solution” without the extraction step is a common error.
Not a promise of exact optimality. Randomization does not erase the integrality gap. The method obtains a proved approximation relative to the relaxation and hence to the optimum; exactness occurs only in special structures.

Scope of Application¶

Randomized rounding belongs primarily to approximation algorithms, combinatorial optimization, and operations research. The classical theory treats 0–1 integer programs and rational LP relaxations for routing, multicommodity flow, matching, packing, and related selection problems.^[1] Standard expositions develop applications to satisfiability, facility location, scheduling, congestion, covering, and network design, with linearity of expectation and concentration bounds as core tools.^[5]

The scope also includes non-LP relaxations. Semidefinite rounding maps vector or matrix solutions to cuts, assignments, or signs through random geometric objects. Dependent rounding handles constraints that independent choices would disrupt by coupling variables while preserving marginals and tightly controlling sums.^[6] Path-based rounding samples from a fractional-flow decomposition instead of treating edge variables independently. Pipage, swap, and related randomized schemes use movements within a polytope to reach vertices while retaining expectation or correlation properties.

The relaxation need not be solved to exact optimum for the abstraction to apply. If the fractional solver returns a point with a certified objective bound, the rounding analysis can compose with that solver's error. Nor must the final implementation remain random: derandomization can turn the probabilistic construction into a deterministic approximation algorithm. What cannot be removed is the analyzed distribution derived from the relaxed solution; without it, the method becomes another rounding or approximation paradigm.

Clarity¶

Randomized rounding clarifies the division of labor between optimization and probability. The relaxation answers, “what would an ideal divisible solution look like, and what bound does it certify?” The rounding distribution answers, “how should indivisible choices imitate that fractional geometry?” The probabilistic analysis answers, “which imitation errors can occur together, and how likely are they?” The extraction step answers, “how does a proof of a good event become an efficient output?”

This separation prevents three recurrent confusions. First, a good expected objective does not imply feasibility. Second, high probability of feasibility does not by itself control objective loss. Third, comparison to the relaxation is not automatically comparison to the integral optimum unless the inequality direction is stated. In a minimization problem, \(LP^*\le OPT\); proving a feasible rounded cost at most \(\alpha LP^*\) gives cost at most \(\alpha OPT\). In a maximization problem, \(SDP^*\ge OPT\); proving expected rounded value at least \(\alpha SDP^*\) gives at least \(\alpha OPT\).

Manages Complexity¶

The technique separates a globally coupled discrete problem into a tractable fractional plan and a controlled random realization. Fractional optimization can exploit convexity, duality, separation oracles, and efficient solvers; probability can then manage the combinatorial collision created when divisible mass becomes indivisible choices. This avoids searching the full discrete space directly.

Randomization also compresses constructive reasoning. Instead of specifying one integral choice at a time while maintaining every invariant, a designer specifies a distribution whose moments are easy to compute. Linearity of expectation handles the objective without requiring independence. Concentration and correlation tools handle collective constraints. Derandomization can be postponed until after the clean random proof reveals which conditional quantity must be maintained.

The modularity supports refinement. If independent rounding fails a cardinality constraint, replace the distribution with dependent rounding while retaining marginals. If a union bound is too weak, exploit negative correlation or a local lemma. If failure probability is only constant, repeat. If sampling is undesirable, fix choices by conditional expectation. Each repair targets a named interface rather than redesigning the entire approximation algorithm.

Abstract Reasoning¶

For a binary minimization problem, let \(F\subseteq\{0,1\}^n\) be the feasible set and let \(P\subseteq[0,1]^n\) be a tractable relaxation containing \(F\). Solve

\[ LP^*=\min\{c^Tx:x\in P\} \]

to obtain \(x^*\). Independent rounding produces \(X_i\sim\mathrm{Bernoulli}(x_i^*)\), so

\[ \mathbb E[c^TX]=\sum_i c_i\mathbb E[X_i]=c^Tx^*=LP^*. \]

This calculation licenses an objective statement but says nothing about \(X\in F\). The next reasoning step is to express infeasibility as bad events \(B_1,\ldots,B_m\), choose the distribution or scaling so that

\[ \Pr[\text{objective loss is excessive}]+\sum_j\Pr[B_j]<1, \]

or obtain a stronger joint bound. Then a good outcome has positive probability. If its probability is bounded below and a successful result is efficiently recognizable, repetition makes the construction algorithmic. If an efficiently computable conditional estimator remains below one, choices can be fixed deterministically.^[4]

This proof template also diagnoses impossibility. If preserving the natural marginals makes a constraint fail with constant probability across too many rows, independent rounding is structurally mismatched. Scaling changes expectation to buy feasibility; dependence changes joint behavior while preserving marginals; alteration repairs sparse failures. The distribution is an algorithm-design variable, not a ritual consequence of \(x^*\).

Knowledge Transfer¶

The role structure transfers widely within discrete optimization. A new application asks: Which hard constraint should be relaxed? What fractional statistic should the discrete solution preserve? Which random object realizes that statistic? What are the bad events? Which inequality matches their dependency structure? Can success be detected, repaired, amplified, or derandomized? Those questions transfer from routing to covering, scheduling, facility location, cuts, assignments, and submodular optimization.

Specific probability rules do not transfer blindly. Independent Bernoulli rounding is natural for unconstrained selections but can destroy an exact budget. Hyperplane rounding is meaningful for vector geometry but not a generic LP. Negative-correlation properties may hold only for named families of subsets. A Chernoff bound requires appropriate independence or negative dependence. The reusable knowledge is therefore the design loop—relax, encode, sample, bound, extract—not one universal formula.

Outside approximation algorithms, numerical stochastic rounding and survey sampling show analogous expectation-preserving maps. That resemblance is informative but insufficient for prime status. The optimization relaxation, integral feasibility family, approximation ratio, and integrality-gap reasoning remain indispensable domain cargo.

Examples¶

Independent coordinate rounding. Given \(x^*\in[0,1]^n\), select item \(i\) independently with probability \(x_i^*\). Every coordinate preserves its marginal and every linear objective preserves its fractional value in expectation. If the only requirement is an expected objective, this may suffice. If the solution must select exactly \(k\) items, however, the sample size fluctuates; this failure motivates dependent rounding rather than an unsupported claim of feasibility.

Scaled set-cover rounding. For universe \(U\) with \(m=|U|\), let fractional set variables satisfy \(\sum_{S\ni e}x_S^*\ge1\) for every element \(e\). Select each set independently with probability \(p_S=\min\{1,\lambda x_S^*\}\). If no containing set has probability one, then

\[ \Pr[e\text{ uncovered}]=\prod_{S\ni e}(1-p_S)\le e^{-\lambda}. \]

Taking \(\lambda=\ln(4m)\) makes the union-bound probability of any uncovered element at most \(1/4\). Expected cost is at most \(\lambda LP^*\), so Markov's inequality bounds the probability that cost exceeds \(2\lambda LP^*\) by \(1/2\). Hence a feasible cover of cost at most \(2\ln(4m)LP^*\) appears with probability at least \(1/4\). The constants are illustrative; the structural point is the explicit cost–coverage tradeoff purchased by scaling.

Randomized routing. Decompose each commodity's fractional flow into a distribution over paths, then independently choose one path for each commodity with the decomposition weights. Expected edge load equals fractional edge load. Concentration inequalities control excess congestion across edges; the result turns a divisible multicommodity flow into unsplittable routes with a proved load bound. Routing and packing were foundational applications of the technique.^[1]

MAX CUT hyperplane rounding. The semidefinite relaxation assigns a unit vector \(v_i\) to every vertex. Sample a random hyperplane through the origin and put vertices on sides according to the sign of \(v_i\cdot r\). If two vectors meet at angle \(\theta_{ij}\), their endpoints are separated with probability \(\theta_{ij}/\pi\). Comparing that probability with the relaxation contribution \((1-\cos\theta_{ij})/2\) gives the Goemans–Williamson guarantee greater than 0.87856 in expectation.^[3] This is randomized rounding even though no coordinate is simply rounded with probability equal to itself.

Dependent bipartite rounding. For fractional edge values in a bipartite graph, coordinated updates can preserve each edge marginal, round every vertex's fractional degree to its floor or ceiling, and establish useful negative-correlation properties. Gandhi and colleagues use this structure in routing, broadcast scheduling, capacitated vertex cover, and fair scheduling.^[6] The example shows that dependence is often the feature that preserves feasibility, not a defect to eliminate.

Structural Tensions¶

Marginal fidelity versus joint feasibility. Setting \(\Pr[X_i=1]=x_i^*\) preserves linear expectations, but constraints depend on joint outcomes. Independence offers clean tail bounds yet may violate exact sums; dependence can preserve sums but requires new correlation analysis.

Relaxation strength versus solution cost. A stronger LP or SDP can reduce the integrality gap and support a better rounding rule, but may be harder to formulate or solve. A weak relaxation can make every subsequent rounding analysis lose, regardless of ingenuity.

Objective preservation versus constraint slack. Scaling covering probabilities upward improves feasibility but increases cost. Scaling packing probabilities downward reduces overload but sacrifices objective. The approximation ratio records this exchange rather than making it disappear.

Clean random proof versus deterministic output. Randomization often makes the construction and analysis transparent. Conditional expectations can remove runtime randomness, but only when the relevant conditional quantity or pessimistic estimator is efficiently computable; the deterministic implementation may be more technical than the proof it follows.

Expectation versus tail guarantee. An expected approximation ratio allows rare poor outcomes. Applications requiring reliability need concentration, repetition, truncation, or an always-feasible rounding design. Stating only the expectation hides this operational distinction.

Repair versus bias. Altering an infeasible draw can restore constraints, but the repair may destroy marginal or objective guarantees. A sound analysis includes the repair cost; it does not treat post-processing as free.

Structural–Framed Character¶

Randomized rounding is strongly structural within a formal domain frame. Its defining relations—relaxation containment, probability marginals, expectation, correlations, feasibility events, objective comparison, and approximation bounds—are mathematical. No institutional role, social value, or interpretive convention supplies its identity.

Its domain framing is nevertheless substantial. “Integral solution,” “LP/SDP relaxation,” “polynomial time,” “integrality gap,” “approximation ratio,” and “derandomization” belong to theoretical computer science and operations research. The abstract skeleton can inspire other expectation-preserving discretizations, but importing the name outside an analyzed optimization construction would erase the commitments that make the method useful.

Structural Core vs. Domain Accent¶

The structural core is a controlled conversion from a divisible surrogate to an indivisible realization: use the surrogate to parameterize a distribution, preserve selected statistics, bound bad joint outcomes, and extract a satisfactory realization. This core explains why the technique feels related to sampling, allocation, and probabilistic existence proofs.

The domain accent is the reason this remains domain-specific: a combinatorial feasible family, a tractable mathematical-programming relaxation, an integral optimum, polynomial-time construction, objective and constraint inequalities, approximation ratios, and integrality-gap consequences. Existing primes already capture Approximation, Probability, Expected Value, and Conditional Probability separately. Their combination does not yield the specialized relaxation-to-integral algorithmic proof pattern without the domain machinery.

Approximation — strict prerequisite and proposed parent. The method deliberately replaces exact discrete optimization with a tractable relaxation and produces a feasible result whose loss is bounded relative to the true optimum. Without a declared approximation guarantee or existence/gap bound, random discretization is not the retained identity.
Optimization. The relaxation and the integral problem each optimize a declared objective under constraints; the relaxation value is meaningful because of its inequality relation to the discrete optimum.
Probability. The rounding distribution, good and bad events, and success guarantees use a specified probability space rather than informal chance.
Expected Value. Marginal preservation and linearity of expectation connect fractional objective values to random integral objectives even when rounded variables are dependent.
Conditional Probability. Derandomization fixes choices while monitoring a conditional expectation or pessimistic estimator; each partial assignment renormalizes the remaining random experiment.
Randomization. There is a surface relation through deliberate chance assignment, but the current live Randomization prime is centered on experimental-design assignment for causal inference. It is therefore a prose neighbor rather than the proposed parent.

Relationships to Other Abstractions¶

Current abstraction Randomized Rounding Domain-specific

Parents (1) — more general patterns this builds on

Randomized Rounding presupposes Approximation Prime

Approximation — strict prerequisite and proposed parent. The method deliberately replaces exact discrete optimization with a tractable relaxation and produces a feasible result whose loss is bounded relative to the true optimum.

Hierarchy path (1) — routes to 1 parentless root

Randomized Rounding → Approximation → Representation → Abstraction

Neighborhood in Abstraction Space¶

Randomized Rounding sits in a sparse region of the domain-specific corpus (87^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Randomized Rounding versus Approximation: Approximation is the broad target–surrogate–error relation. Randomized rounding is one specialist way to construct a discrete approximation from a mathematical-programming relaxation. Greedy, primal–dual, local-search, dynamic-programming, and embedding algorithms can approximate without randomized rounding.

Randomized Rounding versus Randomization: the live Randomization prime assigns experimental units to conditions to support causal inference. Randomized rounding assigns discrete algorithmic choices according to a relaxation-derived law to support an approximation proof. Both use chance, but their inputs, warrants, outputs, and failure modes differ.

Randomized Rounding versus Monte Carlo Simulation: Monte Carlo estimates quantities or simulates distributions through repeated sampling. Randomized rounding constructs a discrete optimization candidate. Repetition may be used to amplify success, but estimation is not its defining output.

Randomized Rounding versus the Probabilistic Method: a probabilistic-method proof can sample a structure from any useful distribution to show existence. Randomized rounding specifically couples the distribution to a relaxation solution of the current instance and normally carries an algorithmic complexity and approximation guarantee.

Independent versus dependent randomized rounding: these are branches of one family, not synonyms for the whole. Independent rounding offers simple marginals and concentration; dependent rounding adds correlation to preserve sums, degrees, assignments, or other coupled constraints.

Randomized rounding versus randomized algorithms generally: quicksort, randomized hashing, skip lists, and randomized search use chance without rounding a relaxation. Chance is necessary here but not sufficient.

Randomized rounding versus stochastic numerical rounding: stochastic arithmetic chooses adjacent representable numbers to reduce numerical bias. Unless it rounds a combinatorial relaxation into a feasible optimization object with a proved objective relation, it remains a different numerical abstraction.

References¶

[1] Prabhakar Raghavan and Clark D. Thompson, “Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs,” Combinatorica 7(4) (1987), 365–374. https://doi.org/10.1007/BF02579324; author-hosted paper. The foundational paper maps rational relaxations of 0–1 programs to provably good integer solutions and develops routing, flow, matching, and integrality-gap applications. registry ↩a ↩b ↩c

[2] Aravind Srinivasan, “Approximation Algorithms via Randomized Rounding: A Survey,” in Lectures on Approximation and Randomized Algorithms (1999). Author-hosted survey. The survey defines randomized rounding as mapping an efficiently computed relaxation optimum back to a feasible instance solution and reviews correlation inequalities and applications. registry ↩

[3] Michel X. Goemans and David P. Williamson, “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming,” Journal of the ACM 42(6) (1995), 1115–1145. https://doi.org/10.1145/227683.227684; author-hosted paper. The primary paper verifies randomized hyperplane rounding of an SDP relaxation and the expected >0.87856 MAX CUT guarantee. registry ↩a ↩b

[4] Prabhakar Raghavan, “Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs,” Journal of Computer and System Sciences 37(2) (1988), 130–143. https://doi.org/10.1016/0022-0000(88)90003-7. The primary paper develops deterministic algorithms that mimic randomized-rounding existence proofs through conditional-probability machinery. registry ↩a ↩b

[5] David P. Williamson and David B. Shmoys, “Random Sampling and Randomized Rounding of Linear Programs,” chapter 5 in The Design of Approximation Algorithms (Cambridge University Press, 2011), 99–136. https://doi.org/10.1017/CBO9780511921735.006; electronic book. The authoritative textbook chapter supports the LP-rounding family, expected guarantees, applications, and conditional-expectation derandomization boundary. registry ↩a ↩b

[6] Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan, “Dependent Rounding and Its Applications to Approximation Algorithms,” Journal of the ACM 53(3) (2006), 324–360. https://doi.org/10.1145/1147954.1147956; author-hosted paper. The primary paper verifies marginal preservation, degree preservation, negative-correlation properties, and multiple approximation-algorithm applications. registry ↩a ↩b