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 m by the maximum number of edges per path. It likewise gives a modest improvement in the running time.



Localized rounding scheme

  input: instance {\cal I}=(\mbox{graph } G, \mbox{set of paths } P, \mbox{capacities } (C,c), \mbox{values } v)
  output: integer flow \tilde f for {\cal I}
0. Compute a maximum-size fractional multicommodity flow f^*.
1. Let \tilde c = 3(1+\varepsilon )\ln (d)/\varepsilon ^2 where d=\max _{p\in P} |p|.
2. Initialize \tilde{f_ p}=0 for every path p\in P.
3. Define P’(\tilde f) = \{ p\in P\, |\, \forall e\in p.~ \tilde f(e) \lt c_ e\} (the non-saturated paths).
4. Repeat until all paths in P are saturated:
5. For each path p\in P’(\tilde f), define \delta _ p = \lfloor \min _{e\in E} \min (c_ e-\tilde f(e), c_ e/\tilde c) \rfloor .
6. Choose path p\in P’(\tilde f) randomly from distribution q on P’(\tilde f), where q_ p = \alpha \, f^*_ p / \delta _ p (choosing \alpha so that |q|=1).
7. Increase \tilde{f_ p} by \delta _ p.
8. Return \tilde f.
Lemma.

Let d be the maximum number of capacity constraints on any path. For any \varepsilon \in (0,1) such that \min _{e\in C} c_ e \ge \tilde c = 3(1+\varepsilon )\ln (d)/\varepsilon ^2, the flow \tilde f returned by the rounding scheme is feasible and has expected size at least |f^*|/(1+\varepsilon ).

Proof.

Fix any instance {\cal I}. For any path p, let {\cal I}_ p be the subproblem of {\cal I} obtained by deleting all capacity constraints from {\cal I} except those on edges in p, and giving value v_ p to path p and value zero to all other paths.

For any given path p, if we were to run the original rounding scheme on {\cal I}_ p with fractional flow f^*, the existence proof for that rounding scheme implies that it would give \tilde{f_ p} expectation at least f^*_ p/(1+\varepsilon ). Since the localized rounding scheme will increment \tilde{f_ p} as much (or more)1 than that rounding scheme would, the localized scheme also gives \tilde{f_ p} expectation at least f^*_ p/(1+\varepsilon ).

By linearity of expectation, summing over the paths, in expectation, the value v(\tilde f) of the flow \tilde f returned by the localized scheme is at least \sum _ p v_ pf^*_ p/(1+\varepsilon ) = v(f^*)/(1+\varepsilon ).

 
 

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 {\cal I}_ p of the individual paths.

Localized algorithm

  input: instance {\cal I}=(\mbox{graph } G, \mbox{set of paths } P, \mbox{capacities } (C,c), \mbox{values } v)
  output: integer flow \tilde f for {\cal I}
1. Let \tilde c = 3(1+\varepsilon )\ln (d)/\varepsilon ^2 where d=\max _{p\in P} |p|.
2. Initialize \tilde{f_ p}=0 for every path p\in P.
3. Define P’(\tilde f) = \{ p\in P\, |\, \forall e\in p.~ \tilde f(e) \lt c_ e\} (the non-saturated paths).
4. Repeat until all paths in P are saturated:
5. Choose p\in P minimizing \sum _{e\in p} w_ e/v_ p, where w_ e =\infty if e is saturated; else w_ e = (1+\varepsilon )^{\tilde c\, \tilde f(e) / c_ e}.
6. Increase \tilde f_ p by \delta _ p = \lfloor \min _{e\in E} \min (c_ e-\tilde f(e), c_ e/\tilde c) \rfloor .
7. Return \tilde f.

The conditional expectation of the final flow value, given the current flow \tilde f, is at least the pessimistic estimator \psi (\tilde f) ~ =~ \sum _{p\in P} v_ p\, \psi _ p(\tilde f), 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 \psi (\tilde f) 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 1/c_ e.)

The performance guarantee follows as a corollary:

Theorem (localized algorithm).

Let d be the maximum number of capacity constraints on any path. For any \varepsilon \in (0,1) such that the minimum edge capacity is at least 3(1+\varepsilon )\ln (d)/\varepsilon ^2, the value v(\tilde{f_ p}) of the flow \tilde f returned by the algorithm is at least v(f^*)/(1+\varepsilon ), where f^* is a maximum-value feasible flow.

The number of iterations taken by the algorithm is at most 1+6 \min (m, \rho ) (1+\varepsilon )\ln (d)/\varepsilon ^2, where \rho = |f^*|/\min _{e\in C} c_ e 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 p’ that overlaps with p may acquire a saturated edge before p does, which can allow p to be incremented for longer.

MathJax is loading, equations are not yet displayed...