19.17 Randomized Rounding

Many optimization problems can be expressed as integer programs. Variables represent decisions, constraints describe feasibility requirements, and an objective function measures solution quality. Unfortunately, integer programs are often computationally difficult to solve exactly.

A common strategy is to relax the problem. Instead of requiring variables to be integers, allow them to take fractional values. The resulting linear program can usually be solved efficiently. The challenge then becomes converting the fractional solution back into a valid integer solution.

Randomized rounding provides an elegant answer. Each fractional value becomes a probability. Random choices transform the fractional solution into a discrete one while preserving important properties of the original optimization problem.

This technique has become one of the foundational tools of approximation algorithms.

Problem

Consider a simple optimization problem.

Variables:

x₁, x₂, x₃

Integer requirements:

xᵢ ∈ {0,1}

Suppose the linear-programming relaxation produces:

x₁ = 0.8
x₂ = 0.3
x₃ = 0.6

These values are not valid integer solutions.

How can we convert them into:

0
or
1

while preserving solution quality?

Basic Idea

Interpret each fractional value as a probability.

Example:

x₁ = 0.8

becomes:

Choose x₁ = 1
with probability 0.8

Choose x₁ = 0
with probability 0.2

Similarly:

x₂ = 0.3

becomes:

Choose x₂ = 1
with probability 0.3

Choose x₂ = 0
with probability 0.7

Each variable is rounded independently.

Simple Example

Fractional solution:

x₁ = 0.8
x₂ = 0.3
x₃ = 0.6

Possible rounded result:

x₁ = 1
x₂ = 0
x₃ = 1

Another run might produce:

x₁ = 1
x₂ = 1
x₃ = 0

The output varies.

The analysis focuses on expected behavior.

Implementation

import random

def randomized_round(
    value: float,
) -> int:
    return (
        1
        if random.random() < value
        else 0
    )

Usage:

solution = [
    0.8,
    0.3,
    0.6,
]

rounded = [
    randomized_round(x)
    for x in solution
]

print(rounded)

Possible output:

[1, 0, 1]

Expected Value Preservation

This is the key property.

Suppose:

x = 0.8

Rounded variable:

X

Then:

P(X = 1) = 0.8
P(X = 0) = 0.2

Expected value:

E[X]
=
1(0.8)
+
0(0.2)
=
0.8

Therefore:

E[X] = x

Randomized rounding preserves expectations.

This simple fact powers most analyses.

Linear Objectives

Suppose the objective is:

maximize

3x₁ + 5x₂ + 2x₃

Fractional solution:

x₁ = 0.8
x₂ = 0.3
x₃ = 0.6

LP value:

3(0.8)
+
5(0.3)
+
2(0.6)

=
5.1

After randomized rounding:

X₁
X₂
X₃

Expected objective:

E[
3X₁
+
5X₂
+
2X₃
]

Using linearity of expectation:

=
3E[X₁]
+
5E[X₂]
+
2E[X₃]

which becomes:

=
3(0.8)
+
5(0.3)
+
2(0.6)

=
5.1

Expected objective value remains unchanged.

Why LP Relaxation Matters

Integer program:

xᵢ ∈ {0,1}

Relaxation:

0 ≤ xᵢ ≤ 1

The LP solution provides:

A lower bound

for minimization problems, or:

An upper bound

for maximization problems.

Randomized rounding converts this fractional solution into a feasible discrete solution.

The quality of the rounded solution can then be compared to the LP optimum.

Set Cover Example

Suppose:

S₁
S₂
S₃

are candidate sets.

LP solution:

x₁ = 0.7
x₂ = 0.5
x₃ = 0.2

Interpretation:

Choose S₁
with probability 0.7

Choose S₂
with probability 0.5

Choose S₃
with probability 0.2

The resulting collection of chosen sets becomes a random cover candidate.

Analysis determines how likely all elements remain covered.

Vertex Cover Example

For each vertex:

v

LP solution produces:

x(v)

Randomized rounding selects:

v

with probability:

x(v)

The expected cover size equals the LP objective value.

Additional analysis bounds the probability that edges remain uncovered.

Failure Probability

Randomized rounding does not automatically guarantee feasibility.

Example:

Constraint:

x₁ + x₂ ≥ 1

Fractional solution:

x₁ = 0.5
x₂ = 0.5

Randomized rounding may produce:

0 + 0

violating the constraint.

Probability:

0.5 × 0.5
=
0.25

Constraint failure occurs.

Additional techniques are needed.

Amplification

One common solution repeats the rounding process.

Instead of:

Choose once.

choose multiple times.

Example:

Probability of failure

=
0.25

Two independent repetitions:

0.25²
=
0.0625

Three repetitions:

0.25³
=
0.015625

Failure probability decreases rapidly.

Chernoff Bounds

Randomized rounding analyses frequently use Chernoff bounds.

These inequalities estimate how far a random variable deviates from its expectation.

Example:

Expected value = 100

Question:

How likely is
the result below 80?

Chernoff bounds show:

Exponentially unlikely.

These bounds provide rigorous guarantees for randomized approximation algorithms.

Coverage Probability

Suppose an element belongs to sets:

S₁
S₂
S₃

LP values:

0.4
0.5
0.3

Probability the element remains uncovered:

(1 - 0.4)
(1 - 0.5)
(1 - 0.3)

=
0.21

Coverage probability:

0.79

Repeating the rounding process improves coverage.

This idea appears repeatedly in approximation algorithms.

Derandomization

Randomized rounding is often only the first step.

After proving a randomized algorithm works:

Convert it
into a deterministic algorithm.

This process is called derandomization.

Techniques include:

• Method of conditional expectations
• Pessimistic estimators
• Deterministic rounding

Many famous approximation algorithms began as randomized constructions.

Scheduling Example

Suppose jobs may be assigned fractionally:

Machine A: 0.7
Machine B: 0.3

for a given task.

Randomized rounding converts:

Fractional assignment

into:

Actual machine choice

while approximately preserving load balance.

Large-scale scheduling systems often use variants of this idea.

Facility Location Example

LP solution:

Open facility A: 0.9
Open facility B: 0.2
Open facility C: 0.6

Randomized rounding:

Open A with probability 0.9
Open B with probability 0.2
Open C with probability 0.6

The expected opening cost matches the LP solution.

Approximation analysis bounds the resulting service cost.

Why Randomization Helps

Deterministic rounding often introduces systematic bias.

Example:

Round up if ≥ 0.5

Fractional values:

0.49
0.49
0.49
...

all become:

0

Large errors accumulate.

Randomized rounding preserves expectations exactly.

This makes analysis much easier.

Complexity

Suppose:

n

variables appear in the LP solution.

Randomized rounding requires:

O(n)

time.

Each variable generates one random decision.

Memory overhead is minimal.

The expensive step is solving the LP itself.

Common Applications

Randomized rounding appears in:

• Set cover
• Vertex cover
• Facility location
• Scheduling
• Resource allocation
• Network design
• Load balancing
• Clustering
• Routing
• Packing problems

It is one of the most versatile techniques in approximation algorithms.

Common Mistakes

Ignoring Constraint Violations

A rounded solution may violate constraints.

Additional analysis is usually necessary.

Assuming Independence Unnecessarily

Some constraints require correlated rounding.

Independent rounding may be insufficient.

Forgetting Expectation vs Guarantee

Expected objective value does not imply every execution performs well.

Concentration analysis is often required.

Using Deterministic Thresholds

Threshold rounding can destroy useful probabilistic properties.

Randomized rounding preserves expectations.

Discussion

Randomized rounding is one of the central ideas connecting probability theory and approximation algorithms. A fractional solution from a linear program becomes a probability distribution over feasible decisions. Random choices transform that distribution into an actual solution while preserving expected objective values.

The technique succeeds because expectation is easy to analyze. Once expectations are established, concentration inequalities such as Chernoff bounds provide high-probability guarantees. The resulting algorithms often achieve approximation ratios that are difficult or impossible to obtain through purely deterministic methods.

The next section explores primal-dual approximation algorithms, another major framework for designing approximation algorithms. Unlike randomized rounding, primal-dual methods derive approximate solutions directly from the structure of the optimization problem and its dual formulation.