Randomized Rounding of Linear Programs into Integer Solutions

Many combinatorial optimization problems become linear programs when the constraint that variables be integers is dropped. The relaxation can be solved in polynomial time, and its optimal value is a lower bound on the integer optimum. Rounding the fractional solution back to integers is where the approximation ratio is decided, and randomized rounding is the version of the idea that lets the rounding error be analysed as a sum of independent random variables.

The technique is simple to state: solve the relaxation, then treat each fractional value as a probability and round each variable independently by a coin flip with that bias. The expected cost is exactly the relaxation value for linear objectives, so the approximation ratio follows from the expectation alone. The constraints are where the difficulty lies, because an expectation over the objective says nothing about feasibility, and repairing feasibility can cost more than the rounding saved.

Set cover as the worked example

The set cover problem: given a universe of m elements and a collection of n sets with costs, choose a minimum-cost subcollection covering every element. Its relaxation assigns a value x_S in [0,1] to each set, minimizes sum c_S x_S subject to sum over sets containing e of x_S ≥ 1 for every element e. The constraint matrix has one row per element and one column per set, and the relaxation’s optimum OPT_LP is a lower bound on the integer optimum.

Randomized rounding picks each set S independently with probability x_S. The expected cost is exactly sum c_S x_S = OPT_LP, by linearity. That part is clean and needs no inequality.

Feasibility is the problem. For an element e covered by sets with values x_1, ..., x_k summing to at least 1, the probability that none of them is picked is prod (1 - x_i), which is at most (1 - 1/k)^k < 1/e when the values are equal and the element is covered by k sets. The element remains uncovered with probability up to about 1/e, and with m elements the expected number of uncovered elements is up to m/e. Simply accepting that leaves a constant fraction uncovered, which is not a feasible solution.

The repair is to repeat the rounding a logarithmic number of times. After t independent roundings, an element is uncovered with probability at most e^{-t}, and the union bound over m elements gives a probability below 1 when t exceeds ln m. The cost of the union of t roundings is at most t · OPT_LP in expectation, so the approximation ratio is O(log m). That is the classical result, and the analysis is exactly the union bound from Concentration Inequalities for Algorithm Analysis applied to a random number of trials.

The alternative repair is to include every element’s cheapest set at the end, which costs at most m · OPT_LP and is worse. The repeated-rounding repair is the one that gives the logarithmic ratio, and the logarithm is not an artifact: set cover has no constant-factor approximation unless P equals NP, so a logarithmic ratio is essentially the best available for the general problem.

The dependence between constraints

The union bound over elements is valid but pessimistic, because the events “element e is uncovered” are not independent: a set that covers several elements affects all of them at once. For the feasibility argument the dependence does not matter, since the union bound does not require independence. For sharper results it does.

A sharper analysis groups the elements by the structure of the sets covering them. If each element is covered by many sets with small values, the probability of being uncovered is closer to e^{-1} than to (1-1/k)^k, and if the sets are large, a single set covers many elements and the failures cluster. The clustering is what makes the simple union bound tight in the worst case: an instance with m elements each covered by a single distinct set forces every set to be picked, and the relaxation value is the integer optimum, so the ratio is 1. The worst case for the ratio is the opposite: many elements covered by overlapping sets with values summing to 1.

The grouped analysis can improve the ratio to O(log m / log log m) for certain instances, but the improvement depends on the structure and is not uniform. For the general problem the O(log m) bound from the union bound is what the standard treatments present, and the refinements are noted as instance-specific.

Integrality gaps and what rounding cannot fix

The ratio achieved by randomized rounding is bounded below by the integrality gap of the relaxation: the supremum over instances of the integer optimum divided by the relaxation optimum. No rounding scheme, randomized or not, can beat that ratio for the given relaxation, because the relaxation’s value is a lower bound and the integer optimum is what it is.

For set cover the integrality gap of the natural relaxation is Θ(log m), which is why the repeated-rounding ratio matches it. For other problems the gap is smaller. For vertex cover the natural relaxation has an integrality gap of 2, and a simple rounding that takes every vertex whose value is at least 1/2 gives a 2-approximation deterministically, with no randomness needed. For the max-cut problem the relaxation is a semidefinite program rather than a linear one, and the rounding is a random hyperplane through the origin, which gives an expected ratio of about 0.878.

The pattern is that the relaxation determines the achievable ratio, and the rounding technique determines how close to the gap the algorithm gets. Randomized rounding gets within the gap for set cover; for vertex cover it does no better than threshold rounding; for max-cut the randomized hyperplane is what achieves the known constant.

Repairing feasibility without losing the objective

The set cover repair multiplies the cost by the number of repetitions. A more careful approach adjusts the rounding probabilities so that constraints are satisfied with higher probability before any repetition, at the cost of a small increase in the expected objective.

One such adjustment solves the relaxation with slightly tightened constraints: replace sum x_S ≥ 1 with sum x_S ≥ 1 + δ for a small δ, which raises the relaxation value by a factor of 1 + δ and reduces the probability that an element is uncovered to about e^{-(1+δ)}. The gain is a constant factor in the exponent, which reduces the number of repetitions needed from ln m to ln m / (1+δ). The cost is a 1 + δ factor in the objective. Choosing δ balances the two, and the optimum is at a small constant, giving a ratio of O(log m) with a better constant.

A different repair handles constraints of the form “at most one of these variables is 1”, which arise in packing problems. Independent rounding violates such a constraint whenever two variables in the same group both round to 1, and the expected number of violations is the sum of pairwise products. Conditional rounding, which rounds the variables of a group sequentially and stops when one is chosen, preserves the constraint exactly but changes the marginal probabilities, so the objective analysis must be redone for the conditional distribution.

import random

def round_with_repair(x, constraints, tries):
    """x: fractional values in [0,1]. constraints: list of index lists,
    each requiring at least one member rounded to 1."""
    for _ in range(tries):
        chosen = {i for i, p in enumerate(x) if random.random() < p}
        if all(any(i in chosen for i in c) for c in constraints):
            return chosen
    # Fallback: satisfy every constraint by taking its cheapest member.
    for c in constraints:
        if not any(i in chosen for i in c):
            chosen.add(min(c, key=lambda i: x[i]))
    return chosen

The fallback is what makes the procedure always return a feasible set; the loop is what makes the cost close to the relaxation value with high probability. The analysis of the loop uses the per-constraint failure probability and the union bound, and the analysis of the fallback bounds the additional cost by the number of unsatisfied constraints times the largest single value.

Why randomization is used when a deterministic rounding exists

For many relaxations a deterministic rounding rule achieves the same ratio: threshold at 1/2, or round to the nearest integer, or use the structure of the constraint matrix to round along an extreme point. The deterministic rules are preferable when they exist, because they remove the failure probability and the entropy requirement.

Randomized rounding is used when no deterministic rule achieves the gap. The set cover case is the clearest: threshold rounding at any fixed value leaves elements uncovered in the worst case, and the deterministic algorithms that achieve O(log m) use a greedy set-covering rule rather than a rounding of the relaxation. Randomized rounding gives a proof that the relaxation’s value is achievable up to the gap, and the proof is constructive.

The technique also serves as an analysis tool for algorithms that were not designed as roundings. A greedy algorithm’s choices can often be coupled to a rounding of a fractional solution, and the coupling shows that the greedy cost is within the gap of the relaxation. The randomization is in the analysis rather than in the code, and the algorithm itself may be deterministic.

The connection to the rest of the cluster is at the level of the tools. The expectation of the rounded objective is linearity, as in Randomized Recurrences and the Indicator Variable Method. The feasibility argument is a union bound over independent events, as in The Probabilistic Method. The gap between the expected cost and the cost of one run is closed by repetition and a tail bound, as in Concentration Inequalities for Algorithm Analysis. What is specific to rounding is the source of the probabilities: they are not chosen for convenience but read off a solved linear program, and the quality of the resulting algorithm is capped by the integrality gap of that program.