Lagrangian relaxation / example

A simple example of a Lagrangian-relaxation algorithm.

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



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.

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 [1]). 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.

Footnotes

  1. 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}. \]

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