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. |
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 ).
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
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:
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
- 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.