# Multicommodity Flow III: better approximation via localization

Strengthening the approximation ratio by “localizing” the analysis.

Localizing the previous existence proof improves the approximation ratio, replacing the number of edges by the maximum number of edges per path. It likewise gives a modest improvement in the running time.

# Localized rounding scheme

 input: instance output: integer flow for 0. Compute a maximum-size fractional multicommodity flow . 1. Let where . 2. Initialize for every path . 3. Define (the non-saturated paths). 4. Repeat until all paths in are saturated: 5. For each path , define . 6. Choose path randomly from distribution on , where (choosing so that ). 7. Increase by . 8. Return .
Lemma.

Let be the maximum number of capacity constraints on any path. For any such that , the flow returned by the rounding scheme is feasible and has expected size at least .

Proof.

Fix any instance . For any path , let be the subproblem of obtained by deleting all capacity constraints from except those on edges in , and giving value to path and value zero to all other paths.

For any given path , if we were to run the original rounding scheme on with fractional flow , the existence proof for that rounding scheme implies that it would give expectation at least . Since the localized rounding scheme will increment as much (or more)1 than that rounding scheme would, the localized scheme also gives expectation at least .

By linearity of expectation, summing over the paths, in expectation, the value of the flow returned by the localized scheme is at least .

Next we apply the method of conditional probabilities to derive the algorithm. As usual for a localized scheme, the pessimistic estimator is the value-weighted sum of the pessimistic estimators of the subproblems of the individual paths.

# Localized algorithm

 input: instance output: integer flow for 1. Let where . 2. Initialize for every path . 3. Define (the non-saturated paths). 4. Repeat until all paths in are saturated: 5. Choose minimizing , where if is saturated; else . 6. Increase by . 7. Return .

The conditional expectation of the final flow value, given the current flow , is at least the pessimistic estimator where

$\psi _ p(\tilde f) ~ =~ f_ p ~ +~ [p\in P’(\tilde f)]\, {\textstyle \frac{\ln (1+\varepsilon )}{\tilde c\, \varepsilon }}\, \Big[\tilde c – \operatorname {smax}_{e\in p} \frac{\tilde f(e) \tilde c}{c_ e} \Big] \, f^*_ p.$

The algorithm above makes each choice to keep from decreasing, guaranteeing a successful outcome. (Curiously, this algorithm differs from the non-localized algorithm in that it does not scale the edge weights by .)

The performance guarantee follows as a corollary:

Theorem (localized algorithm).

Let be the maximum number of capacity constraints on any path. For any such that the minimum edge capacity is at least , the value of the flow returned by the algorithm is at least , where is a maximum-value feasible flow.

The number of iterations taken by the algorithm is at most , where is the “width” of the problem instance.

(The iteration bound has the same proof as for the non-localized algorithm.)

## Footnotes

1. It can be more, because in the localized rounding scheme some path that overlaps with may acquire a saturated edge before does, which can allow to be incremented for longer.