CoreSource checked

Randomized Rounding

Turns fractional optimization values into integral choices using probabilities derived from the fractional solution.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Randomness & Sampling
Difficulty: Intermediate
Family: Randomized Approximation
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 2
Code example: Ready
Visualization: Ready

Overview

Randomized rounding solves or receives a relaxed fractional solution, then independently or dependently rounds variables according to those fractional values. The method preserves expected values and is often analyzed with concentration bounds.

Core Concepts

approximation from relaxationsrandomized approximationmatchingrandom samplingrandomness sampling

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use when a fractional relaxation is available and expectation or high-probability guarantees are useful.
Use when deterministic rounding loses too much structure.

When Not to Use

Avoid when constraints must be satisfied exactly in every run unless repair steps are included.
Avoid when random variance is unacceptable and no derandomization is planned.

What It Does

Starts from a fractional relaxation
Rounds variables using probabilities tied to fractional values
Analyzes expected objective value or constraint violation

Use Cases

Approximation algorithms for hard discrete problems
Rounding linear-programming relaxations
Creating randomized integral solutions from fractional plans

Inputs

Fractional LP or relaxation solution vector x* in [0, 1]^n
Problem constraints and PRNG state

Outputs

Rounded integral candidate solution x in {0, 1}^n
Objective value and constraint satisfaction check

Key Formulas (1)

Rounding probability

P(x_i = 1) = fractional_{x i}

P(x_i = 1) = fractional_x_i

Turns fractional variables into binary decisions with matching probabilities.

Pseudocode

1.Compute or receive a fractional solution
2.For each variable, draw a random value
3.Set the variable to 1 when the draw is below its fractional value
4.Check objective and constraints
5.Repair or repeat if the problem requires feasibility guarantees

Canonical Example

Input: fractional choice x = 0.7 for an item
Output: choose the item with probability 0.7
Explanation: Across repeated trials, the rounded variable has expected value 0.7.

Implementation Notes

Keep the fractional solution and rounded solution side by side for checks.
Run enough trials or add repair steps when feasibility is not guaranteed.
Use deterministic seeds in tests and statistical checks in experiments.

Common Pitfalls

Rounding variables independently can violate coupled constraints.
Reporting only expected quality hides high-variance outcomes.
Forgetting to fix the random seed makes examples and tests hard to reproduce.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show turning fractional solutions into integer choices with matching probabilities on a small approximation from relaxations example.

Step 1 of 5: Compute or receive a fractional solution

randomness-sampling-mechanism

Notes

Randomized rounding is usually paired with an approximation analysis, not just a sampling step.

Sources (1)

What each reference supports for this entry.

Randomized Algorithms

Book

Randomized-algorithms reference for Randomized Rounding rounding fractional solutions with probability-based decisions.

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

UsesLinear Programming Simplex Method

Optimization · Core

Randomized rounding often starts from a linear-programming relaxation.

Compare with this

Conceptual neighborGreedy Set Cover