A simple example of a Lagrangian-relaxation algorithm.

The algorithm is for Maximum Multicommodity Flow. It illustrates some prototypical aspects of Lagrangian relaxation.

Click for background material…

the Maximum Multicommodity Flow problem. The input is a graph $G=(V,E)$ , a capacity $c_ e\gt 0$ for each edge $e$ , and a collection $P$ of paths in $G$ . The goal is to assign a non-negative flow value $f_ p$ to each path $p\in P$ so as to maximize the total flow assigned, subject to the constraint that no edge has more flow (on the paths going through the edge) than the capacity of the edge.

We let $f(e)$ denote $\sum _{p\ni e} f_ p$ , the flow $f$ sends along edge $e$ .

The flow is integer if each $f_ p$ is an integer.

Algorithm

To ease presentation, assume that each edge capacity is at least 1. (If not, divide all edge capacities by the minimum edge capacity before running the algorithm.) The algorithm finds a near-maximum multicommodity flow.

	input: graph $G=(V,E)$ with edge capacities; collection $P$ of paths in $G$
	output: multicommodity flow $f$
1.	Let $f_ p \leftarrow 0$ for each $p\in P$ .
2.	Repeat until some edge $e$ has at least $c_ e \ln (m)/\varepsilon$ units of flow through it.
3.	Send $\varepsilon$ units of flow along a path $p$ , where $p\in P$ minimizes $\sum _{e\in p} \exp (f(e)/c_ e)/c_ e$ . (Typically a shortest-path algorithm is used to find $p$ .)
4.	Let $\alpha \leftarrow \max _{e\in E} f(e) / c_ e$ .
5.	Return $f’$ where $f’_ p = f_ p / \alpha$ for $p\in P$ . …Scale $f$ to make it feasible.

Performance guarantee

In the 1990s, the following approximation guarantee was proved for algorithms similar to this one:

Theorem (e.g. [5, 2, 3, 4, 6, 1]).

The algorithm above returns a flow $f$ of size at least $1-O(\varepsilon )$ times maximum.

Click for proof sketch…

The maximum edge congestion (i.e., $\max _ e\, x(e)/c_ e$ ) is at most

\[ \Phi (f) = \ln \sum _ e \exp (f(e)/c_ e). \]

Let $\psi _ e$ denote $\exp (f(e)/c_ e)$ . In an iteration where the algorithm sends $\varepsilon$ units of flow along a path $p$ , the increase in $\Phi$ is at most

\begin{equation} (1+O(\varepsilon )) \varepsilon \frac{\sum _{e\in p} \psi _ e/c_ e}{\sum _ e \psi _ e}. \label{eq:1} \end{equation}

(The bound (\ref{eq:1}) follows by algebra¹, using the inequalities $\exp (\delta ) \le 1+\delta +O(\delta ^2)$ for $\delta \le \varepsilon =O(1)$ and $\ln (1+z)\le z$ .)

Let $f^*$ be an optimal feasible flow. For a random path $p$ chosen from the distribution defined by $f^*/|f^*|$ , the expectation of the numerator in (\ref{eq:1}) is

\[ \sum _ e\Pr [e\in p] \frac{\psi _ e}{c_ e} = \sum _ e \frac{f^*(e)}{|f^*|} \frac{\psi _ e}{c_ e} \le \sum _ e \frac{\psi _ e}{|f^*|} = \frac{\sum _ e \psi _ e}{|f^*|}. \]

Thus, if $p$ is chosen randomly from $f^*/|f^*|$ , the expectation of (\ref{eq:1}) is at most $(1+O(\varepsilon ))\varepsilon /|f^*|$ . Thus, there exists a path $p$ to choose that would keep $\Phi$ from increasing by more than $(1+O(\varepsilon ))\varepsilon /|f^*|$ in the iteration. The algorithm chooses $p$ to minimize (\ref{eq:1}), so in fact $\Phi$ increases by at most $(1+O(\varepsilon ))\varepsilon /|f^*|$ in each iteration of the algorithm.

Since $\Phi$ is initially $\ln m$ , and the flow value $|f|$ increases by $\varepsilon$ in each iteration, it follows by algebra that the algorithm maintains the invariant

\[ \frac{\Phi – \ln (m)}{(1+O(\varepsilon ))/|f^*|} \le |f|. \]

Recall that the maximum edge congestion is at most $\Phi$ . By the termination condition, at termination $\Phi$ is at least $\ln (m)/\varepsilon$ , so the $\ln m$ term in the numerator above is $O(\varepsilon \Phi )$ . Substituting $O(\varepsilon \Phi )$ for $\ln m$ and simplifying gives

\[ \frac{|f|}{\Phi } \ge (1-O(\varepsilon ))|f^*|. \]

Thus, scaling $f$ down by $\Phi$ would give a flow of value $(1-O(\varepsilon ))|f^*|$ . Since the algorithm scales $f$ down by the maximum edge congestion, which is less than than $\Phi$ , the algorithm returns a flow of value at least $(1-O(\varepsilon ))|f^*|$ .

The potential $\Phi$ in the proof combines all the hard edge-capacity constraints into a single smooth function. This is the hallmark of a Lagrangian-relaxation algorithm.

Width-based bound on the convergence rate

Historically, Lagrangian-relaxation algorithms have generally been used heuristically, without proven bounds on their worst-case convergence rates. One of the main contributions of research since the 1990s has been to prove tight worst-case upper bounds on convergence rates, and to find potential functions and step sizes that lead to faster convergence rates.

Lemma.

The algorithm above makes at most $|f^*|\ln (m)/\varepsilon ^2$ iterations.

Proof.

The algorithm scales $f$ down by roughly $\ln (m)/\varepsilon$ at the end. The resulting flow $f’$ is feasible, so has value at most $|f^*|$ . It follows that before scaling $|f|$ has value at most about $|f^*|\ln (m)/\varepsilon$ . Since each iteration increases $|f|$ by $\varepsilon$ , it follows that there are at most $|f^*|\ln (m)/\varepsilon ^2$ iterations.

It is not hard to see that this upper bound is tight for this algorithm on all inputs. (It stops when the maximum edge congestion is about $\ln (m)/\varepsilon$ , so that scaling $f$ down by $\ln (m)/\varepsilon ^2$ gives a flow of value about $|f^*|$ .)

In general, the previous approach gives bounds on the number of iterations that depend on the so-called width of the problem instance. In this case the width is $|f^*|/\min _ e c_ e$ , which is at most $\sum _ e c_ e / \min _ e c_ e$ . In some problems of interest the width can be as small as $O(1)$ , but in general the width can be large.

Width-independent bounds on convergence rates

To reduce the number of iterations, modify the algorithm as follows (following Garg and Könemann ). In each iteration, instead of sending $\varepsilon$ units of flow, send $\varepsilon \, \min _{e\in p} c_ e$ units, where $p$ is the chosen path. It is not hard to modify the proof to show that the approximation ratio continues to hold.

Lemma.

The modified algorithm does at most $\min (m, |f^*|)\, \ln (m)/\varepsilon ^2$ iterations.

Proof.

In each iteration, at least one edge $e\in p$ has its flow increase by $\varepsilon c_ e$ . Thus, within $m\ln (m)/\varepsilon ^2$ iterations, at least one of the $m$ edges $e\in E$ must have flow at least $c_ e \ln (m)/\varepsilon$ , and the algorithm will terminate.

The bound of $|f^*|\ln (m)/\varepsilon ^2$ iterations also holds, because each iteration increases $|f^*|$ by at least $\varepsilon$ .

Exercise: fractional set cover

Given a fractional set cover $x$ , let $x(e) = \sum _{s\ni e} x_ s$ denote the coverage of any element $e$ . Consider the following algorithm for finding an approximately maximum-size fractional set cover:

Start with $x_ s = 0$ for each set $s$ , then, in each iteration add $\varepsilon$ to $x_ s$ where $s$ maximizes $\sum _{e\in s} \exp (-x(e))$ . Stop when every element is covered by at least a total weight of $\ln (m)/\varepsilon ^2$ , and return $x$ , scaled by the minimum element coverage.

Use the potential function $-\ln \sum _ e \exp (-x(e))$ , a lower bound on the minimum coverage of any element $e$ , to show that the algorithm is a $(1-O(\varepsilon ))$ -approximation algorithm. (Hint: show that the potential increases by at least $(1-O(\varepsilon ))\varepsilon /|x^*|$ in each iteration.)

Modify the algorithm to delete elements as soon as their coverage exceeds $\ln (m)/\varepsilon ^2$ . Show that the approximation ratio still holds, and that the resulting algorithm requires $O(m\ln (m)/\varepsilon ^2)$ iterations, where $m$ is the number of elements to be covered.

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]	M. D. Grigoriadis and L. G. Khachiyan. Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optimization, 4(1):86–107, Feb. 1994.
[3]	P. Klein, S. A. Plotkin, C. Stein, and E. Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM J. Comput., 23(3):466–487, June 1994. Preliminary version in STOC’90.
[4]	S. A. Plotkin, D. B. Shmoys, and E. Tardos. Fast approximation algorithms for fractional packing and covering problems. Math. Operations Research, 20(2):257–301, 1995. Preliminary version in FOCS’91.
[5]	F. Shahrokhi and D. W. Matula. The maximum concurrent flow problem. J. ACM, 37:318–334, 1990.
[6]	N. E. Young. Randomized rounding without solving the linear program. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 170–178, San Francisco, California, 22–24 Jan. 1995.

Footnotes

Here is a full proof of bound (\ref{eq:1}). Let $\delta _ e = \varepsilon [e\in p]/c_ e$ denote the increase in congestion on edge $e$ . Using $\delta _ e\le \varepsilon \le 1$ ,
\[ \exp (f(e)/c_ e+\delta _ e) \, =\, \psi _ e\exp (\delta _ e) \, =\, \psi _ e (1+\delta _ e +O(\delta _ e^2)) \, \le \, \psi _ e (1+(1+O(\varepsilon ))\delta _ e). \]

So the increase in $\Phi (f)$ is at most

\[ \textstyle \ln (\sum _ e \psi _ e(1+(1+O(\varepsilon ))\delta _ e)) -\ln (\sum _ e \psi _ e) ~ =~ \displaystyle \ln \frac{\sum _ e \psi _ e(1+(1+O(\varepsilon ))\delta _ e\psi _ e)}{\sum _ e \psi _ e} \]

\[ =~ \ln \Big[1 + (1+O(\varepsilon ))\frac{\sum _ e \delta _ e\psi _ e}{\sum _ e \psi _ e}\Big] ~ \le ~ (1+O(\varepsilon ))\frac{\sum _ e \delta _ e\psi _ e}{\sum _ e \psi _ e}. \]

Notes on algorithms

Lecture notes on algorithms

Lagrangian relaxation / example