# Multicommodity Flow I: Lagrangian relaxation via Chernoff

Randomized rounding yields a Lagrangian-relaxation algorithm for Multicommodity Flow.

Applying the method of conditional probabilities to a sample-and-increment scheme for Multicommodity Flow yields a Lagrangian-relaxation algorithm with an approximation ratio comparable to the algorithm of Plotkin, Shmoys, and Tardos . The existence proof uses a standard Chernoff bound. This leads to exponential penalties (“multiplicative weights”) in the algorithm.

# Rounding scheme for Multicommodity Flow

 input: instance output: integer flow for 0. Compute a maximum-size fractional multicommodity flow . 1. Initialize for every path . 2. Repeat until some edge is saturated 3. Choose path randomly from the distribution . 4. Increase by 1. 5. Return .

If the minimum edge capacity is sufficiently large, then the rounding scheme works with positive probability:

Lemma (existence, ).

Let be the number of edges with capacity constraints. For any such that , with positive probability, the flow returned by the rounding scheme is feasible and has size more than .

The proof idea is that sends total flow at most on the paths crossing any given edge , so, in any given iteration the probability that the flow along increases (by 1) is at most . Applying Chernoff, a calculation shows that event at the end of iteration has probability less than . Hence, the expected number of edges saturated at the end of iteration is less than 1.

Next we apply the method of conditional probabilities to derive the algorithm.

Lemma (algorithm, ).

Applying the method of conditional probabilities to the existence proof yields the following algorithm.

For the derivation, we need a pessimistic estimator for the expectation of the number of edges saturated by iteration , conditioned on the current flow at the end of a given iteration . The proof of the Chernoff bound gives a pessimistic estimator for each edge. Summing over the edges gives the following pessimistic estimator:

# Multicommodity Flow via Chernoff

 input: instance output: integer flow for 1. Initialize for every path . Set . 2. Repeat until some edge is saturated 3. Choose a path minimizing , where (To choose , compute a shortest path in w.r.t. edge weights .) 4. Increase by 1. 5. Return .
$\phi _ t ~ =~ \sum _{e\in C} \frac{ (1+\varepsilon )^{\tilde f(e)} \exp \big ((T-t)\, \varepsilon \, c_ e/|f^*|\big )}{ (1+\varepsilon )^{ c_ e } }.$

Unfortunately, to minimize this pessimistic estimator, the algorithm would need to know .

To fix this, normalize each capacity constraint “” into the equivalent “”, where is the lower bound on . Apply Chernoff to the now-normalized constraints. The proof still goes through, but now gives pessimistic estimator

$\phi ’_ t ~ =~ \sum _{e\in C} \frac{ (1+\varepsilon )^{\tilde f(e) \tilde c / c_ e} \, \exp \big ((T-t)\, \varepsilon \, \tilde c/|f^*|\big ) }{ (1+\varepsilon )^{\tilde c } }.$

The factors in that depend on are independent of (and ), so can be ignored. The algorithm makes each choice to minimize the pessimistic estimator (more precisely, an upper bound on it; see the verification of below). Hence, it guarantees a successful outcome.

Theorem ().

Let be the number of edges with capacity constraints. For any such that , given the graph , the set of paths , the capacity constraints , and , the algorithm above returns a feasible integer flow whose size is at least , where is any maximum-size feasible flow.

Algorithms with comparable performance guarantees were given (for example) by Plotkin, Shmoys, and Tardos  and by Grigoriadis and Khachiyan .

# Discussion

Many technical questions remain. How do we find approximately optimal fractional solutions? How do we obtain a fast (strictly polynomial-time) algorithm? Can we generalize to other packing and covering problems?

Fractional solutions can be obtained simply by scaling the capacities (given any , scale so , then the algorithm will give a -approximate solution). Polynomial time can be ensured using Garg and Könemann’s non-uniform increments. And, yes, the approach generalizes to other problems. We address these questions in detail in other entries.

## Related ## Questions for later

Can one formalize the notion of shifting slack into a pessimistic estimator to make it maximally oblivious?