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.

Click for background material…

Multicommodity Flow II: width-independence using non-uniform increments (for maximum-value Multicommodity Flow)
Greedy Set Cover III: weighted H(d)-approximation via localization (for the idea of localization)

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)¹ 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$ .)

Click for verification of pessimistic estimator…

We reuse the proof details of the non-localized scheme to show that the localized algorithm maintains the invariant $\psi (\tilde f) \ge v(f^*)/(1+\varepsilon )$ , and that the invariant implies the performance guarantee.

1. The invariant holds initially: $(\psi (\overline0) \ge v(f^*)/(1+\varepsilon ))$ .

From the end of the proof details in the non-localized scheme, recall that $\psi _p(\overline0) \ge f^*_p/(1+\varepsilon )$ for each $p\in P$ . Taking the weighted sum over $p$ shows $\psi (\overline0) \ge v(f^*)/(1+\varepsilon )$ .

2. The algorithm chooses each path to keep $\psi (\tilde f)$ from decreasing.

Consider the pessimistic estimator $\psi _{p'}(\tilde f)$ for any given path $p'\in P$ . From the proof details, when a path $p$ is chosen in a given iteration, this pessimistic estimator $\psi _{p'}(\tilde f)$ increases by at least

$\delta _p [p'=p] ~ -~ \frac{\sum _{e\in p\cap p'} \delta _p w_e/c_e}{\sum _{e'\in p'} w_{e'}} f^*_{p'}.$

where $w_{e}=(1+\varepsilon )^{\tilde f(e) \tilde c/c_e}$ . (And if $p'$ leaves $P'(\tilde f)$ , that can only increase $\psi _{p'}(\tilde f)$ more.)

Taking the weighted sum over $p$ , the pessimistic estimator $\psi (\tilde f)$ increases by at least $\delta _p$ times

$\begin{align} & v_p ~ -~ \sum _{p'\in P'} \frac{\sum _{e\in p\cap p'} w_e/c_e}{\sum _{e'\in p'} w_{e'}} v_{p'} f^*_{p'} \notag \\ ~ =~ & v_{p} ~ -~ \sum _{e\in p} w_{e} \sum _{p'\in P', p'\ni e} \frac{f^*_{p'}}{c_{e}} \Big[\frac{v_{p'}}{\sum _{e'\in p'}w_{e'}}\Big]. \label{desired} \end{align}$

The algorithm chooses the path $p \in P'$ to maximize the ratio $v_{p} / \sum _{e'\in p} w_{e'}$ , which then dominates the ratio in square brackets for each $p'\in P'$ in \eqref{desired} above, making sure \eqref{desired} is at least

$\begin{align} & v_{p} \, - \, \Big[\frac{v_{p}}{\sum _{e\in p} w_e}\Big] \sum _{e\in p} w_e \sum _{p' \in P', p'\ni e} \frac{f^*_{p'}}{c_{e}} & (\text{by the choice of } p' ) \notag \\ ~ \ge ~ & v_{p} \, - \, \Big[\frac{v_{p}}{\sum _{e\in p} w_e}\Big] \sum _{e\in p} w_{e} & (\text{since } f^*(e) \le c_{e}) \notag \\ ~ =~ & 0. \notag \end{align}$

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

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.

Notes on algorithms

Lecture notes on algorithms

Multicommodity Flow III: better approximation via localization

Localized rounding scheme

Localized algorithm

Footnotes