Speeding up the algorithm by increasing the step size.

The previous rounding schemes increase the chosen variable $\tilde x_j$ by 1 with each sample. This can be exponentially slow. To speed it up, we modify the rounding scheme (or algorithm) to take larger steps, with the step size varying each iteration. Here we use the idea to speed up the Multicommodity-Flow algorithm.

This specific algorithm comes from Garg and Könemann [1, 2, 3], although the basic idea (called a trust region) is well known.

While we’re at it, we also generalize the algorithm to handle maximum-weight Multicommodity Flow.

Click for background material…

The “slow” Multicommodity-Flow algorithm
Analyzing a scheme with a random stopping time
Maximum-weight Multicommodity Flow (click for definition)

An instance is specified by a regular instance of Multicommodity flow, along with a weight (or value) $v_p$ for each path $p$ . The value $v(f)$ of a flow $f$ is then $\sum _{p\in P} v_p f_p$ . The goal is to find a feasible flow of maximum value. For the algorithm, one may require that the value $v_p$ of flow along a path $p$ depends only on, say, the commodity that the path serves.

Rounding scheme with non-uniform increments

	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-value fractional multicommodity flow $f^*$ .
1.	Initialize $\tilde{f_p}=0$ for every path $p\in P$ . Let $\tilde c = 3(1+\varepsilon )\ln (m)/\varepsilon ^2$ .
2.	Repeat until some edge is saturated $(\exists e\in C.~ \tilde f(e) = c_e):$
3.	For each path $p\in P$ , define increment $\delta _p = \lfloor \min _{e\in C} \min (c_e-\tilde f(e), c_e/\tilde c) \rfloor$ , then choose path $p\in P$ randomly from the probability distribution $q$ such that $q_p = \alpha \, f^*_p / \delta _p$ (choosing $\alpha$ so that $\|q\|=1$ ).
4.	Increase $\tilde{f_p}$ by $\delta _p$ .
5.	Return $\tilde f$ .

For each sample, the scheme fixes an increment $\delta _p\gt 0$ for each path $p$ , then samples a random path $p$ and increases the flow on the sampled path $\tilde{f_p}$ by $\delta _p$ (instead of 1). The sampling distribution is chosen so that the expected increase in each variable $\tilde{f_p}$ is $\alpha \, f^*_p$ for some $\alpha$ .

Lemma (existence).

Let $m$ be the number of edges with capacity constraints. For any $\varepsilon \in (0,1)$ such that $\min _e c_e \ge \tilde c = 3(1+\varepsilon )\ln (m)/\varepsilon ^2$ , the flow $\tilde f$ returned by the rounding scheme is feasible and has expected value at least $v(f^*)/(1+\varepsilon )$ .

Because the analysis must use a random stopping time, the standard Chernoff bound doesn’t quite give the right proof. We adapt Chernoff to handle the random stopping time. It is possible to adapt it to give a tail bound on the probability of failure, but instead we adapt it to bound the expected flow size directly. This allows us to localize the bound later.

Define

$\psi (\tilde f) ~ =~ v(\tilde f) ~ +~ {\textstyle \frac{\ln (1+\varepsilon )}{\tilde c\, \varepsilon }}\, \Big[\tilde c - \operatorname {smax}_{e\in C} \frac{\tilde f(e) \tilde c}{c_e} \Big] \, v(f^*)$

where $\operatorname {smax}_{e\in C} z_e ~ =~ \log _{1+\varepsilon }{\textstyle \sum _{e\in C}} (1+\varepsilon )^{z_e}.$ This is a smooth approximation to $\max _{e\in C} z_e$ .

To prove the lemma we show that $\psi (\tilde f)$ is a valid pessimistic estimator for the conditional expectation of the final flow size, and has initial value at least $|f^*|/(1+\varepsilon )$ .

For the case of unit values $(v_p=1)$ , in fact, $\psi (\tilde f)$ is the (linearly scaled and translated)¹ logarithm of the pessimistic estimator $\phi$ for the algorithm for the “slow” multicommodity flow algorithm. The calculations in this proof are somewhat forbidding, but they are essentially just the calculations underlying that proof in a different guise.

Click for proof details…

i) At termination, the flow value $v(\tilde f)$ is at least $\psi (\tilde f)$ .

Note that $\operatorname {smax}_{e\in C} z_e$ is an upper bound on $\max _{e\in C} z_e$ . At termination, some edge $e$ is saturated, so $\max _{e\in C} \tilde f(e) \tilde c/c_e$ is at least $\tilde c$ , so $\operatorname {smax}_{e\in C} \tilde f(e) \tilde c/c_e$ is also at least $\tilde c$ . Hence, in $\psi (\tilde f)$ , the factor $[\tilde c-\cdots ]$ in square brackets is negative, so $\psi (\tilde f)$ is at most $v(\tilde f)$ .

ii) The quantity $\psi (\tilde f)$ is a sub-martingale.

At the start of a given iteration, let $p$ be the path chosen in the iteration. Let $\Delta _e$ denote the increase in the flow $\tilde f(e)$ on edge $e\in C$ during the iteration: $\Delta _e = [e\in p] \delta _p$ .

Consider first the increase in $\operatorname {smax}_{e\in C} \tilde f(e) \tilde c/c_e$ . Let $w_e=(1+\varepsilon )^{\tilde f(e) \tilde c/c_e}$ denote the summand for $e$ in the sum inside the $\operatorname {smax}$ . The rounding scheme’s restrictions on $\delta _p$ ensure that $\Delta _e\tilde c/c_e \in [0,1]$ for each edge $e$ . Using this and $(1+\varepsilon )^z \le 1+\varepsilon z$ for $z\in [0,1]$ , the iteration increases the sum inside the $\operatorname {smax}$ from $\sum _e w_e$ to

$\begin{align*} \sum _{e} w_e (1+\varepsilon )^{\Delta _e \tilde c/c_e} ~ & \le ~ \sum _{e} w_e (1+\varepsilon \Delta _e \tilde c/c_e) \\ ~ & =~ \Big(\sum _{e} w_e\Big) \Big(1+\frac{\varepsilon \tilde c \sum _{e} w_e \Delta _e/c_e}{\sum _{e}w_e}\Big). \end{align*}$

Using $\log _{1+\varepsilon }[W (1+Z)] =\log _{1+\varepsilon }(W)+\log _{1+\varepsilon }(1+Z) \le \log _{1+\varepsilon }(W) + Z/\ln (1+\varepsilon )$ , it follows that the value of $\operatorname {smax}_{e\in C} \tilde f(e) \tilde c/c_e$ itself increases by at most

$\frac{\varepsilon \, \tilde c}{\ln (1+\varepsilon )} \frac{\sum _{e} w_e \Delta _e/c_e}{\sum _{e} w_e}.$

In turn, it follows that the value of $\psi (\tilde f)$ increases by at least

$\begin{equation} \label{eqn:pess2} \delta _p v_p ~ -~ \frac{\sum _{e} w_e \Delta _e/c_e}{\sum _{e} w_e} v(f^*) ~ =~ \delta _p v_p ~ -~ \frac{\sum _{e\in p} \delta _p w_e/c_e}{\sum _{e} w_e} v(f^*). \end{equation}$

The expectation of $\delta _p v_p$ is $\sum _p (\alpha f^*_p/\delta _p) v_p\delta _p = \alpha v(f^*)$ . The expectation of each $\Delta _e$ is $\sum _{p\ni e} (\alpha f^*_p/\delta _p)\delta _p \le \alpha c_e$ . Hence, the lower bound above has non-negative expectation.

iii) At any time during the rounding scheme, the conditional expectation of the final flow value at termination, given the current flow $\tilde f$ , is at least $\psi (\tilde f)$ .

Point (i) implies that the conditional expectation of the final flow value at termination is at least the conditional expectation of $\psi (\tilde f)$ at termination. Point (ii) above and Wald’s equation imply that the latter is at least the current value of $\psi (\tilde f)$ .

From point (iii) above it follows that, at the start of the rounding scheme, the expected value of the final flow is at least $\psi (\overline0)$ , which by calculation and the choice of $\tilde c = 3(1+\varepsilon )\ln (m)/\varepsilon ^2$ is

$\begin{align*} & \frac{\ln (1+\varepsilon )}{\tilde c\, \varepsilon }\Big[\tilde c - \frac{\ln m}{\ln (1+\varepsilon )}\Big] v(f^*) \\ ~ =~ & \frac{\ln (1+\varepsilon )}{\varepsilon }\Big[1 - \frac{\varepsilon ^2}{3(1+\varepsilon )\ln (1+\varepsilon )}\Big] v(f^*) \\ ~ \ge ~ & \frac{1}{1+\varepsilon }\, v(f^*). \end{align*}$

The latter inequality above follows by algebra from $(1+\varepsilon )\ln (1+\varepsilon ) \ge \varepsilon +\varepsilon ^2/3$ for $\varepsilon \in [0,1]$ . (Not coincidentally this is the same inequality that is used at the end of the proof of Chernoff.)

Algorithm with non-uniform increments

	input: instance ${\cal I}=(\mbox{graph } G, \mbox{set of paths } P, \mbox{capacities } c, \mbox{values } v)$
	output: integer flow $\tilde f$ for ${\cal I}$
1.	Initialize $\tilde{f_p}=0$ for every path $p\in P$ . Let $\tilde c = 3(1+\varepsilon )\ln (m)/\varepsilon ^2$ .
2.	Repeat until some edge is saturated $(\exists e\in C.~ \tilde f(e) = c_e):$
3.	Choose path $p\in P$ to minimize $\sum _{e\in p} w_e/(v_pc_e)$ , where $w_e = (1+\varepsilon )^{\tilde f(e) \tilde c / c_e}$ .
4.	Increase $\tilde{f_p}$ by $\delta _p = \lfloor \min _{e\in C} \min (c_e-\tilde f(e), c_e/\tilde c) \rfloor$ .
5.	Return $\tilde f$ .

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

We simply reuse the pessimistic estimator $\psi (\tilde f)$ (on the conditional expectation of the final flow size) from the existence proof. The algorithm chooses the path $p$ in each iteration to keep the pessimistic estimator from decreasing, and so guarantees a successful outcome.

Click for details…

Bound \eqref{eqn:pess2} of the existence proof shows that in a given iteration the pessimistic estimator increases by at least

$\delta _p v_p ~ -~ \frac{\sum _{e\in p} \delta _p w_e/c_e}{\sum _{e\in C} w_e} v(f^*)$

and that there is always a path $p\in P$ that makes this lower bound non-negative. Gathering terms that depend on $p$ (and factoring out $\delta _p$ ) this lower bound is non-negative for a given $p$ iff

$\textstyle \sum _{e\in p} w_e/(v_pc_e) \le (\sum _{e\in C} w_e) |f^*|.$

Since the algorithm chooses $p$ to minimize the left-hand side above, the choice guarantees that the above inequality holds, so that the choice of $p$ does not decrease the pessimistic estimator. Hence, at termination the pessimistic estimator is at least its initial value. As shown in the existence proof, this implies that the final flow size is at least $|f^*|/(1+\varepsilon )$ .

The performance guarantee follows:

Theorem ([1, 2, 3]).

Let $m=|C|$ be the number of capacity constraints. For any $\varepsilon \in (0,1)$ such that $\min _{e\in C} c_e \ge 3(1+\varepsilon )\ln (m)/\varepsilon ^2$ , given the graph $G$ , the set of paths $P$ , and $\varepsilon$ , the algorithm above returns a feasible integer flow $\tilde f$ whose value is at least $v(f^*) / (1+\varepsilon )$ , where $f^*$ is any maximum-value feasible flow.

Finally, we bound the number of iterations that the algorithm (and rounding scheme) take.

Theorem ([1, 2, 3]).

The number of iterations taken by the algorithm is at most $1+6 \min (m, \rho ) (1+\varepsilon )\ln (m)/\varepsilon ^2$ , where $\rho = |f^*|/\min _{e\in C} c_e$ is the “width” of the problem instance.

Proof.

Recall $\tilde c = 3(1+\varepsilon )\ln (m)/\varepsilon ^2$ , so the desired bound is $2\min (m, \rho ) \tilde c$ .

Each iteration except the last increases the flow on some edge $e\in p$ (the bottleneck edge, the one determining the minimum in the definition of $\delta _p$ ) by $\lfloor c_e/\tilde c \rfloor$ , which is at least $0.5 c_e/\tilde c$ , so the number of iterations (before some edge is saturated) is at most $2m \tilde c$ .

Each iteration except the last increases the total flow $|\tilde f|$ by at least $\lfloor \min _{e\in C} c_e/\tilde c \rfloor$ , which is at least $0.5 \min _{e\in C} c_e/\tilde c$ , so the number of iterations is at most $2 |\tilde f| \tilde c / \min _{e\in C} c_e \le 2\rho \tilde c$ .

Bibliography

[1]	N. Garg and J. Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Thirty Ninth Annual Symposium on Foundations of Computer Science, pages 300–309, 1998.
[2]	N. Garg and J. Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM Journal on Computing, 37:630, 2007. Preliminary version in FOCS’98 (pp. 300–309).
[3]	J. Könemann. Fast combinatorial algorithms for packing and covering problems. Master’s thesis, Universität des Saarlandes, 1998.

Footnotes

Let $\phi (\tilde f)$ denote that pessimistic estimator with $T=|f^*|/(1+\varepsilon )$ . Then
$\psi (\tilde f) = \frac{|f^*|}{1+\varepsilon } - \frac{|f^*| \ln (1+\varepsilon )}{\tilde c\, \varepsilon } \log _{1+\varepsilon } \phi (\tilde f).$

For intuition, note that if $\phi (\tilde f)$ is a super-martingale, then so is $\log _{1+\varepsilon } \phi (\tilde f)$ , which would make $\psi (\tilde f)$ a sub-martingale. But note that we haven’t in fact shown that $\phi (\tilde f)$ is a super-martingale with respect to the rounding scheme with increments.

Notes on algorithms

Lecture notes on algorithms

Multicommodity Flow II: width-independence via non-uniform increments

Rounding scheme with non-uniform increments

Algorithm with non-uniform increments

Related

Bibliography

Footnotes