Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts.
This paper describes new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities. These algorithms are much faster than algorithms discovered previously. Besides being an important problem in its own right, the uniform-capacity concurrent flow problem has many interesting applications.  Leighton and Rao used uniform-capacity concurrent flow to find an approximately "sparsest cut" in a graph and thereby approximately solve a wide variety of graph problems, including minimum feedback arc set, minimum cut linear arrangement, and minimum area layout. However, their method appeared to be impractical as it required solving a large linear program. This paper shows that their method might be practical by giving an $O(m^2 \log m)$ expected-time randomized algorithm for their concurrent flow problem on an $m$-edge graph.  Raghavan and Thompson used uniform-capacity concurrent flow to solve approximately a channel width minimization problem in very large scale integration.  An randomized algorithm and an $O(k\min{n,k} (m+n\log n)\log k)$ deterministic algorithm is given for this problem when the channel width is $\Omega(\log n)$, where $k$ denotes the number of wires to be routed in an $n$-node, $m$-edge network.
Introduction
The multicommodity flow problem involves shipping several different commodities from their respective
sources to their sinks in a single network with the total amount of flow going through an edge
limited by its capacity. The amount of each commodity we wish to ship is called the demand for
that commodity. An optimization version of this problem is the concurrent flow problem in which
the goal is to find the maximum percentage z such that at least z percent of each demand can be
shipped without violating the capacity constraints. Here we consider the concurrent flow problem
with unit capacities. Observe that in this case, the problem is equivalent to the problem of finding a
flow (disregarding capacities) that minimizes the maximum total flow on any edge (the congestion).
Let m, n, and k be, respectively, the number of edges, nodes, and commodities for the input network.
In this paper, we give algorithms that, for any positive ffl, find a solution whose congestion is no
more than (1 times the minimum congestion. Our algorithms significantly improve the time
required for finding such approximately optimal solutions.
One contribution of this paper is the introduction of a randomization technique useful in iterative
approximation algorithms. This technique enables each iteration to be carried out much more quickly
than by using known deterministic methods.
Part of our motivation in developing algorithms for concurrent flow derives from two important
applications, finding sparsest cuts and finding a VLSI routing that minimizes channel width.
Leighton and Rao [11] showed how to use the solution to a unit-capacity concurrent flow problem
to find an approximate "sparsest cut" of a graph. As a consequence, they and other researchers have
developed polylog-times-optimal approximation algorithms for a wide variety of graph problems,
including minimum area VLSI layout, minimum cut linear arrangement, minimum feedback arc set
[11], optimal linear and higher-dimensional arrangement [5], minimum chordal fill [7], and single-processor
scheduling [14].
The computational bottleneck of the method of Leighton and Rao is solving a unit-capacity
concurrent flow problem with O(n) commodities, each with unit demand. They appealed to linear
programming techniques to show that the problem can be solved in polynomial time. The new
approximation algorithm greatly improves the resulting running time.
Theorem 1.1 For any fixed ffl ? 0, a (1 ffl)-factor approximation to the unit-capacity, unit-demand
concurrent flow problem can be found by a randomized algorithm in O((k + m)m log m) expected time,
where the constant depends on ffl.
As an application of this result we substantially reduce the time required for Leighton and Rao's
method.
Theorem 1.2 An O(log n)-factor approximation to the sparsest cut in a graph can be found by a
randomized algorithm in expected O(m 2 log m) time.
The previous best running time of O(n 4:5
log n) [18], is obtained by using linear programming
techniques and fast matrix multiplication.
Another application of our approximation algorithm is to VLSI routing in graphs. Raghavan
and Thompson [13] and Raghavan [12] considered the problem of routing two-terminal nets (es-
sentially wires) in a graph so as to approximately minimize the channel width, i.e., the maximum
number of nets routed through an edge. The computational bottleneck in their algorithms is solving
a unit-capacity concurrent flow problem. Their algorithms require a better than constant ffl approximation
to the concurrent flow problem. In fact, the algorithm of Theorem 1.1 is a fully polynomial
approximation algorithm, i.e. its running time depends polynomially on ffl \Gamma1 .
Algorithm type Running Time
Randomized, fixed ffl O(m(k +m) log n)
Deterministic, fixed ffl O(mk(k +m) log n)
poly(n) O(ffl \Gamma3 m(k m) log 2 n)
poly(n) O(ffl \Gamma2 mk(k m) log 2 n)

Table

1: Upper bounds on the running times of our algorithms. The actual bounds are slightly
better.
Theorem 1.3 For any positive ffl ! 1 that is at least inverse polynomial in n, a
to the unit-capacity concurrent flow problem can be found by a randomized algorithm
in expected time O((ffl and by a deterministic algorithm in time
An application of the algorithm of Theorem 1.3 is a significant improvement in the time needed
to solve Raghavan and Thompson's problem.
Theorem 1.4 If w min denotes the minimum achievable channel width and w min
=\Omega\Gamma450 m), a routing
of width w min +O( p
w min log n) can be found by a randomized algorithm in expected time O(k 3=2 (m+
log n)); and by a deterministic algorithm in time O(k min fn; kg (m log n) log k).
Our algorithms compare favorably to previous work. The concurrent flow problem can be formulated
as a linear program in O(mk) variables and O(m+ nk) constraints (see, for example [15]).
Linear programming can be used to solve the problem optimally in polynomial time. Kapoor and
gave a method to speed up the matrix inversions involved in Karmarkar type algorithms
for multicommodity flow problems; combining their technique with Vaidya's new linear programming
algorithm using fast matrix multiplication [18] yields a time bound of O(k 3:5 n 3 p
for the unit-capacity concurrent flow problem with integer demands (where D denotes the sum of
the demands) and an O(
for the approximation problem.
Shahrokhi and Matula [15] gave a combinatorial fully polynomial approximation scheme for the
unit-capacity concurrent flow problem (which they called the concurrent flow problem with uniform
capacities). Their algorithm runs in O(nm 7 ffl \Gamma5 ) time.
Our approach to solving concurrent flow problems is a modification of the framework originated
by Shahrokhi and Matula [15]. The idea is to use a length function on the edges to reflect congestion,
and iteratively reroute flow from long (more congested) paths to short (less congested) paths. Our
approach differs from that of Shahrokhi and Matula in several ways. We develop a framework of
relaxed optimality conditions that allows us to measure the congestion on both a local and a global
level, thereby giving us more freedom in choosing which flow paths to reroute at each iteration. We
exploit this freedom by using a faster randomized method for choosing flow paths. In addition, this
framework also allows us to achieve greater improvement as a result of each rerouting. In Table 1,
we give upper bounds on the running times for our algorithms. Our actual bounds are slightly better
than those in the table, and are given in more detail in the remainder of the paper. Note that by use
of various combinations of our techniques, we can obtain slightly better bounds than those stated in
Theorems 1.1 and 1.3.
An earlier version of this paper has appeared in [9]. In the earlier version the case when both the
capacities and the demands are uniform was considered separately from the more general case when
only the capacities are assumed to be uniform. The earlier version presented a fast algorithm for the
first case, and a factor of ffl \Gamma1 m slower one for the more general case. In this version we extend the
algorithm for the uniform demand case to work for the more general case with at most a logarithmic
slowdown.
Preliminaries and Definitions
In this section we define the concurrent flow problem, introduce our notation, and give some basic
facts regarding the problem. Concurrent flow is a variant of multicommodity flow, and we start by
giving a formal definition of the latter.
The multicommodity flow problem is the problem of shipping several different commodities from
their respective sources to their sinks in a single network, while obeying capacity constraints. More
precisely, an instance of the multicommodity flow problem consists of an undirected graph
a non-negative capacity cap(vw) for every edge vw 2 E, and a specification of k commodities,
k. The specification for commodity i consists of a source-sink pair s
and a non-negative integer demand d(i). We will denote the maximum demand by d max , the total
demand
by D, the number of nodes by n, the number of edges by m, and the number of
different sources by k   . Notice that k   - n. For notational convenience we assume that m - n,
and that the graph G has no parallel edges. If there is an edge between nodes v and w, this edge is
unique by assumption, and we denote it by vw. Note that vw and wv denote the same edge.
A flow f i in G from node s i to node t i can be defined as a collection of paths from s i to t i , with
associated real values. Let P i denote a collection of paths from s i to t i in G, and let f i (P ) be a
nonnegative value for every P in P i . The value of the flow thus defined is
which is the
total flow delivered from s i to t i . The amount of flow through an edge vw is
A feasible multicommodity flow f in G consists of a flow f i from s i to t i of value d(i) for each
We require that f(vw) - cap(vw) for every edge vw 2 E, where we use
to denote the total amount of flow on the edge vw.
We consider the optimization version of the multicommodity flow problem, called the concurrent
flow problem, and first defined by Shahrokhi and Matula [15]. In this problem the objective is
to compute the maximum possible value z such that there is a feasible multicommodity flow with
demands z \Delta d(i) for every 1 - i - k. We call z the throughput of the multicommodity flow. An
equivalent formulation of the concurrent flow problem is to compute the maximum z such that there
is a feasible flow with demands d(i) and capacities cap(vw)=z.
In this paper we shall focus exclusively on the special case of unit capacities, in which all edge-
capacities are equal. The problem of finding a maximum throughput z can be reformulated in this
special case as follows: ignore capacities, and find a multicommodity flow f that satisfies the demands
and minimizes jf ff(vw)g, the maximum total flow on any edge.
A multicommodity flow f satisfying the demands d(i) is ffl-optimal if jf j is at most a factor (1+ ffl)
more than the minimum possible jf j. The approximation problem associated with the unit-capacity
concurrent flow problem is to find an ffl-optimal multicommodity flow f . We shall assume implicitly
throughout that ffl is at least inverse polynomial in n and at most 1=10. These assumptions are
not very restrictive as they cover practically every case of interest. To find an ffl-optimal flow where
ffl - 1=10, one can just find a 1=10-optimal flow. To find an ffl-optimal flow when 1=ffl is greater than
any polynomial in n, one can run our algorithm. It will work for arbitrarily small ffl, however, the
running time will be slower than the time bounds given, as we will need to manipulate numbers
whose size is exponential in the input. However, if this amount of accuracy is desired, it is more
sensible and efficient to use any polynomial time linear programming algorithm to solve the problem
exactly.
One can define the analogous problem for directed graphs. Our algorithms, and the corresponding
time bounds, easily extend to the directed case by replacing (undirected) edges by (directed) arcs
and paths by directed paths. Henceforth, we will concentrate only on the undirected case.
Linear programming duality gives a characterization of the optimum solution to the concurrent
flow problem. Let R be a nonnegative length function. For nodes v; w 2 V let dist ' (v; w)
denote the length of the shortest path from v to w in G with respect to the length function '. For
a path P we shall use '(P ) to denote the length of P . We shall use j'j 1 to denote
vw2E '(vw), the
sum of the length of the edges. The following theorem is a special case of the linear programming
duality theorem (see, for example, [15]).
Theorem 2.1 For a multicommodity flow f satisfying the demands d(i) and a length function ',
dist
Furthermore, a multicommodity flow f minimizes jf j if and only if there exists a nonzero length function
' for which all of the above terms are equal.
The optimality (complimentary slackness) conditions given by linear programming can be reformulated
in terms of conditions on edges and paths.
Theorem 2.2 A multicommodity flow f has minimum jf j if and only if there exists a nonzero length
function ' such that
1. for every edge vw 2 E either
2. for every commodity i and every path
The goal of our algorithms is to solve the approximation problem, i.e. to find a multicommodity
flow f and a length function ' such that the largest term, jf jj'j 1 , in (1) is within a (1 + ffl) factor of
the smallest term,
dist )d(i). In this case, we say that f and ' are ffl-optimal. Note that if f
and ' are ffl-optimal then clearly f is ffl-optimal. In fact, a multicommodity flow f is ffl-optimal if and
only if there exists a length function ' such that f and ' are ffl-optimal.
3 Relaxed optimality conditions
Theorems 2.1 and 2.2 give two (apparently) different characterizations of exact optimality. Our goal
is to find a flow that satisfies a relaxed version of Theorem 2.1. In order to do so, we will introduce a
relaxed version of Theorem 2.2, the complimentary slackness conditions of linear programming. We
will then show that these relaxed optimality conditions are sufficient to show that the first and last
terms in (1) are within a hence the flow f is ffl-optimal. Our notion of relaxed
optimality is analogous to the notion of ffl-optimality used by Goldberg and Tarjan in the context of
the minimum-cost flow problem [4].
be an error parameter, f a multicommodity flow and ' a length function. Throughout
this section we shall use ffl 0 to denote ffl. We say that a path P 2 P i for a commodity i is ffl-good if
and ffl-bad otherwise. The intuition is that a flow path is ffl-good if it is short in either a relative or an
absolute sense, i.e. it is either almost as short as the shortest possible or it is at most a
small fraction of j'j 1 . We use this notion in defining the following relaxed optimality conditions (with
respect to a flow f , a length function ' and an error parameter ffl):
R1) For every edge
The first condition says that every edge either has a length which is a small fraction of the sum
of the lengths of all edges or is almost saturated. The second condition says that the amount of flow
which is on ffl-bad paths, i.e. long paths, contributes a small fraction of the sum f \Delta '.
The next two lemmas show that the relaxed optimality conditions are sufficient to imply ffl-
optimality. We will first show that Condition R1 implies that the first two terms in (1) are close.
Then we will show that the two conditions together imply that the first and last terms in (1) are close.
Thus we can conclude that the relaxed optimality conditions are sufficient to imply ffl-optimality.
Lemma 3.1 Suppose a multicommodity flow f and a length function ' satisfy relaxed optimality condition
R1. Then
vw
vw jf j'(vw) in two parts. The first part is the sum of the terms
contributed by edges that satisfy jf j - (1 This part of the sum is clearly at most
vw f(vw)'(vw). If vw is an edge whose contribution is not counted in the first part then,
by assumption, '(vw) - ffl 0
Therefore, the sum of all other terms is at most ffl 0 jf jj'j 1 . Thus,
This implies the lemma.
Theorem 3.2 Suppose f and ' and ffl satisfy the Relaxed Optimality Conditions R1 and R2. Then f is
ffl-optimal, i.e. jf j is at most a factor (1 more than the minimum possible.
We need to estimate the ratio of the terms in inequality (1) of Theorem 2.1. Lemma 3.1
estimates the ratio of the first two terms. We shall use this in estimating the ratio of the first and
the last term.
Consider the penultimate term in (1). We break this sum,
the sum over ffl-good paths and the sum over ffl-bad paths. Relaxed optimality condition us
an upper bound of ffl 0
on the sum over the ffl-bad paths, and the definition of an
ffl-good path gives us the following bound on the sum over the ffl-good paths:
(dist
Observing that (minfD; kd(i)g)
we can bound the
sum over the ffl-good paths by
dist
dist
Now observe that there are exactly k commodities and
so the last term sums to exactly
This gives that
dist
Combining the bounds on the sum over ffl-bad and ffl-good paths we get
dist
By the middle equations in Theorem 2.1,
gives a bound on
vw2E f(vw)'(vw) in terms on jf jj'j 1 . Combining these inequalities and rearranging
terms we get /
dist
Combining the fractions and dropping low order terms we get that
dist
The assumption that ffl - 1=10 implies that ffl 0 - 1=70, which in turn implies that the factor 1+ffl 0
is less than (1 ffl). We combine this bound with inequality (1) to complete the proof.
In the next two sections, we will focus on algorithms which achieve the relaxed optimality conditions

rerouting
In this section, we describe the procedure Reduce that is the core of our approximation algorithms,
and prove bounds on its running time. Given a multicommodity flow f , procedure Reduce modifies
f until either f becomes ffl-optimal or jf j is reduced below a given target value. The approximation
algorithms presented in the next two sections repeatedly call procedure Reduce to decrease jf j by
a factor of 2, until an ffl-optimal solution is found.
The basic step in our algorithms is choosing a flow path and rerouting some flow from this path
to a "better" path. This step closely resembles the basic step in the algorithm of Shahrokhi and
Matula [15]. The main differences are in the way we choose the paths and in the amount of flow
that is rerouted at each iteration.
The key idea is to measure how good the current flow is by using the notion of ffl-optimality,
described in the previous section. Given a flow f and a value ff to be determined later, we use a
length function defined by which reflects the congestion of the edge vw. In other
words, the length of an edge depends on the flow carried by the edge. Given an input ffl, our algorithms
Reduce(f; -; ffl; oe i for
ff
While jf j - and f and ' are not ffl-optimal,
For each edge vw, '(vw) / e fff(vw) .
Call FindPath(f; '; ffl) to find an ffl-bad flow path P and a short path Q with the same endpoints as P .
Reroute oe i units of flow from P to Q.
Return f .

Figure

1: Procedure Reduce.
gradually update f until f and ' (defined by the above formula) become ffl-optimal. Each update
is done by choosing an ffl-bad flow path, rerouting some flow from this path to a much shorter path
(with respect to '), and recomputing the length function. We will prove below that the parameter ff
in the definition of length can be selected so that relaxed optimality condition R1 is always satisfied.
Through iterative reroutings of flow, we gradually enforce relaxed optimality condition R2. When
both relaxed optimality conditions are satisfied then Theorem 3.2 can be used to infer that f is
ffl-optimal.
For simplicity iof presentation, we shall assume for now that the value of the length function
e fff(vw) at an edge vw can be computed in one step from f(vw) and represented in a single
computer word. In Section 4.3 we will remove this assumption and sho that it is sufficient to compute
an approximation to this value, and show that the time required for computing a sufficiently good
approximation does not change the asymptotic running times of our algorithms.
Procedure Reduce (see Figure 1), takes as input a multicommodity flow f , a target value - ,
an error parameter ffl, and a flow quantum oe i for each commodity i. We require that each flow
path comprising f i carries flow that is an integer multiple of oe i . The procedure repeatedly reroutes
units of flow from an ffl-bad path of commodity i to a shortest path. We will need a technical
granularity condition that oe i is small enough for every i to guarantee that approximate optimality is
achievable through such reroutings. In particular, we assume that upon invocation of Reduce, for
every commodity i we have
Upon termination, the procedure outputs an improved multicommodity flow f such that either
jf j is less than the target value - or f is ffl-optimal. (Recall that we have assumed that ffl - 1=10.)
In the remainder of this section, we analyze the procedure Reduce shown in Figure 1. First, we
show that throughout Reduce f and ' satisfy relaxed optimality condition R1. Second, we show
that if the granularity condition is satisfied, the number of iterations in Reduce is small. Third,
we give an even smaller bound on the number of iterations for the case in which the flow f is O(ffl)-
optimal upon invocation of Reduce. This bound will be used in Section 5 to analyze an ffl-scaling
algorithm presented there. Fourth, we describe efficient implementations of procedure FindPath.
4.1 Bounding the number of iterations of Reduce
Lemma 4.1 If f is a multicommodity flow, and ff - (7
flow f and the length function relaxed optimality condition R1.
7 f(v; w) for an edge vw 2 E and let ffl 0 denote ffl
7 . Observe that
Hence, we have
e fff (v;w)
We can use the bound on ff in the statement of the lemma to conclude that this last term is at least
7m
ffl . Thus, '(vw) - ffl
At the beginning of Reduce, ff is set equal to (7 As long as jf j - ,
the value of ff is sufficiently large, so by Lemma 4.1, relaxed optimality condition R1 is satisfied.
If we are lucky and relaxed optimality condition then it follows that f and '
are ffl-optimal. Now we show that if R2 is not satisfied, then we can make significant progress. Like
Shahrokhi and Matula, we use j'j 1 as a measure of progress.
Lemma 4.2 Suppose oe i and - satisfy the granularity condition. Then rerouting oe i units of flow
from an ffl-bad path of commodity i to the shortest path with the same endpoints decreases j'j 1 by
be an ffl-bad path from s i to t i , and let Q be a shortest (s
. The only edges whose length changes due to the rerouting are those in A [B. The
decrease in j'j 1 is which can also be written as
The granularity condition, the definition of ff, and the assumption that ffl - 1=10, imply that
70 , we have e x
140 x, and e \Gammax
140 x.
Thus the decrease is at least140 ffoe i
Now, observe that is the same as '(P
This gives a lower bound of140 ffoe i ('(P
But P is ffl-bad, so this must be at least140 ffoe i (ffl
We have seen that 7+ffl
which implies that 139ffl 0 - 141ffoe i and therefore the first term
dominates the second term. Thus the third term gives a lower bound on the decrease in j'j 1 .
Substituting the value of ff and using the fact that during execution of Reduce we have - jf j,
yields the claim of the lemma.
The following theorem bounds the number of iterations in Reduce.
Theorem 4.3 If, for every commodity i, - and oe i satisfy the granularity condition and jf
initially then the procedure Reduce terminates after O(ffl
iterations.
Proof : Theorem 3.2 implies that if f and ' satisfy the relaxed optimality conditions then they are
ffl-optimal. By Lemma 4.1, relaxed optimality condition R1 is maintained throughout all iterations.
The fact that f is not yet ffl-optimal implies that condition R2 is not yet satisfied. Hence there exists
an ffl-bad path for FindPath to find. A single rerouting of flow from an ffl-bad path of commodity
i to a shortest path results in a reduction in j'j 1 of at
that every O(max i
log iterations reduce j'j 1 by at least
a constant factor.
Next we bound the number of times j'j 1 can be reduced by a constant factor. Let f 0 denote the
input multicommodity flow. For every edge vw, f 0 (vw) - jf 0 j. Hence after we first assign lengths
to edges, the value of j'j 1 is at most me ffjf 0 j . The length of every edge remains at least 1 so j'j 1
is always at least m. Therefore, j'j 1 can be reduced by a factor of e at most ffjf 0 j times, which is
by the assumption that O(-) and the value of ff. This proves that Reduce
terminated in the claimed number of iterations.
Theorem 4.4 Suppose that the input flow f is O(ffl)-optimal, oe and - satisfy the granularity condition,
and initially. Then the procedure Reduce terminates after O(max i
iterations.
denote the input multicommodity flow. The assumption that f 0 is O(ffl)-optimal
implies that jf for every multicommodity flow f . Therefore, the value of j'j 1 is
never less than e (1+O(ffl)) As in Theorem 4.3, the initial value of j'j 1 is at most me ffjf 0 j , so the
number of times j'j 1 can be reduced by a constant factor is O(ffffljf log m), which is O(ffffljf 0
the choice of ff and - . The theorem then follows as in the proof of Theorem 4.3.
4.2 Implementing an Iteration of Reduce
We have shown that Reduce terminates after a small number of iterations. It remains to show
that each iteration can be carried out quickly. Reduce consists of three steps-computing lengths,
executing Findpath and rerouting flow. We discuss computing lengths in Section 4.3. In this section,
we discuss the other two steps.
We now consider the time taken by procedure FindPath. We will give three implementations
of this procedure. First, we will give a simple deterministic implementation that runs in O(k   (m
log n) +n
time, then a more sophisticated implementation that runs in time O(k   n log n+
finally a randomized implementation that runs in expected
time. All of these algorithms use the shortest-paths algorithm of Fredman and
Tarjan [3] that runs in O(m+ n log n) time.
To deterministically find a bad flow path, we first compute, for every source node s i , the length of
the shortest path from s i to every other node v. This takes O(k   (m+n log n)) time. In the simplest
implementation we then compute the length of every flow path in P and compare its length to the
length of the shortest path to decide if the path is ffl-bad. There could be as many as
flow
paths, each consisting of up to n edges, hence computing these lengths takes O
time.
To decrease the time required for FindPath we have to find an ffl-bad path, if one exists, without
computing the length of so many paths. Observe that if there is an ffl-bad flow path for commodity
i then the longest flow path for commodity i must be ffl-bad. Thus, instead of looking for an ffl-bad
path in P i for some commodity i, it suffices to find an ffl-bad path in the directed graph obtained by
taking all flow paths in P i , and treating the paths as directed away from s i . In order to see if there
is an ffl-bad path we need to compute the length of the longest path from s i to t i in this directed
graph. To facilitate this computation we shall maintain that the directed flow graph is acyclic.
Let G i denote the flow graph of commodity i. If G i is acyclic, an O(m) time dynamic programming
computation suffices to compute the longest paths from s i to every other node. Suppose that in an
iteration we reroute flow from an ffl-bad path from s i to t i , in the flow graph G i . We must first update
the flow graph G i to reflect this change. Second, the update might introduce directed cycles in G i ,
so we must eliminate such cycles of flow. We use an algorithm due to Sleator and Tarjan [16] to
implement this process. Sleator and Tarjan gave a simple O(nm) algorithm and a more sophisticated
O(m log n) algorithm for the problem of converting an arbitrary flow into an acyclic flow.
Note that eliminating cycles only decreases the flows on edges, so it cannot increase j'j 1 . Thus
our bound on the number of iterations in Reduce still holds.
We compute the total time required for each iteration of Reduce as follows. In order to implement
FindPath, we must compute shortest path from s i to t i in G and the longest path from s i
to t i in G i for every commodity i, so the time required is O(k   (m
after each rerouting, we must update the appropriate flow graph and eliminate cycles. Elimination
of cycles takes O(m log n) time. Combining these bounds gives an O(k   n log n+m(k+ log n)) bound
on the running time of FindPath.
In fact, further improvement is possible if we consider the flow graphs of all commodities with
the same source and same flow quantum oe i together. Let G v;oe be the directed graph obtained by
taking the union of all flow paths treating each
path as directed away from v. If G v;oe is acyclic, an O(m) time dynamic programming computation
suffices to compute the longest paths from v to every other node in G v;oe .
During our concurrent flow algorithm all commodities with the same demand will have same flow
quantum. To limit the different flow graphs that we have to consider we want to limit the number
of different demands. By decomposing demand d(i) into at most log d(i) demands with source s i
and sink t i we can assume that each demand is a power of 2. This way the number of different flow
graphs that we have to maintain is at most k   log d max .
Lemma 4.5 The total time required for deterministically implementing an iteration of Reduce (as-
suming that exponentiation is a single step) is O(k   n log n +m(logn
Next, we give a randomized implementation of FindPath that is much faster when ffl is not
too small; this implementation seems simple enough to be practical. If f and ' are not ffl-optimal,
then relaxed optimality condition R2 is not satisfied, and thus ffl-bad paths contribute at least an
7 -fraction of the total sum
Therefore, by randomly choosing a flow path P
with probability proportional to its contribution to the above sum, we have at least an ffl
7 chance
of selecting an ffl-bad path. Furthermore, we will show that we can select a candidate ffl-bad path
according to the right probability in O(m) time. Then we can compute a shortest path with the
same endpoints in O(m+n log n) time. This enables us to determine whether or not P was an ffl-bad
path. Thus we can implement FindPath in O(ffl expected time.
The contribution of a flow path P to the above sum is just the length of P times the flow on
so we must choose P with probability proportional to this value. In order to avoid examining all
such flow paths explicitly, we use a two-step procedure, as described in the following lemma.
Lemma 4.6 If we choose an edge vw with probability proportional to '(vw)f(vw), and then we select
a flow path among paths through this edge vw with probability proportional to the value of the flow
carried on the path, then the probability that we have selected a given flow path P is proportional to its
contribution to the sum
Select an edge vw with probability f(vw)'(vw)=B. Once
an edge vw is selected, choose a path
. Consider a
commodity i and a path
Choosing an edge with probability proportional to '(vw)f(vw) can easily be done in O(m) time.
In order to then choose with the right probability a flow path going through that edge, we need a
data structure to organize these flow paths. For each edge we maintain a balanced binary tree with
one leaf for each flow path through the edge, labeled with the flow value of that flow path. Each
internal node of the binary tree is labeled with the total flow value of its descendent leaves. The
number of paths is polynomial in n and ffl \Gamma1 , therefore using this data structure, we can randomly
choose a flow path through a given edge in O(log n) time.
In order to maintain this data structure, each time we change the flow on an edge, we must
update the binary tree for that edge, at a cost of O(log n) time. In one iteration of Reduce the
flow only changes on O(n) edges, therefore the time to do these updates is O(n log n) per call to
FindPath, which is dominated by the time to compute single-source shortest paths.
We have shown that if relaxed optimality condition R2 is not satisfied, then, with probability of
at least ffl=7, we can find an ffl-bad path in O(m log n) time. FindPath continues to pick paths
until either an ffl-bad path is found or 7=ffl trials are made. Observe that given that f and ' are not
yet ffl-optimal (which implies that condition R2 is not yet satisfied), the probability of failure to find
an ffl-bad path in 7=ffl trials is bounded by 1=e. Thus, in this case, Reduce can terminate, claiming
that f and ' are ffl-optimal with probability of at least 1 \Gamma 1=e. Computing lengths and updating
flows can each be done in O(n log n) time, thus we get the following bound:
Lemma 4.7 One iteration of Reduce can be implemented randomly in time (ffl
(assuming that exponentiation is a single step).
The randomized algorithm as it stands is Monte Carlo; there is a non-zero probability that
Reduce erroneously claims to terminate with an ffl-optimal f . To make the algorithm Las Vegas
(never wrong, sometimes slow), we introduce a deterministic check. If FindPath fails to find an
ffl-bad path, Reduce computes the sum
dist to the required precision and compares it
with jf jj'j 1 to determine whether f and ' are really ffl-optimal. If not, the loop resumes. The time
required to compute the sum is O(k   (m n)), because at most k   single-source shortest path
computations are required. The probability that the check must be done t times in a single call to
Reduce is at most (e so the total expected contribution to the running time of Reduce is
at most O(k   (m
Recall that the bound on the number of iterations of Reduce is greater than
which in turn is at least k. Since in each iteration we carry out at least one shortest path computation,
the additional time spent on checking does not asymptotically increase our bound on the running
time for Reduce.
We conclude this section with a theorem summarizing the running time of Reduce for some
cases of particular interest. For all of these bounds the running time is computed by multiplying the
appropriate time for an iteration of Reduce by the appropriate number of iterations of Reduce.
These bounds depend on the assumption that exponentiation is a single step. In Subsection 4.3 we
shall show that the same bounds can be achieved without this assumption. We shall also give a more
efficient implementation for the case when ffl is a constant.
Theorem 4.8 Let f = O(-) and - and oe i satisfy the granularity condition. Let H(k; d;
and let - g. Then the following table contains running times for various implementations
of procedure Reduce (assuming that exponentiation is a single step).
Randomized Implementation Deterministic Implementation
poly(n)
O
O
poly(n)
, O
O
f is O(ffl)-opt.
4.3 Further implementation details
In this section, we will show how to get rid of the assumption that exponentiation can be performed
in a single step. We will also give a more efficient implementation of the procedure Reduce for the
case when ffl is fixed.
4.3.1 Removing the assumption that exponentiation can be performed in O(1) time
To remove the assumption that exponentiation can be performed in O(1) time, we will need to do two
things. First we will show that it is sufficient to work with edge-lengths - '(vw) that are approximations
to the actual lengths We then show that computing these approximate edge-lengths
does not change the asymptotic running times of our algorithms.
The first step is to note that in the proof of Lemma 4.2, we never used the fact that we reroute
flow onto a shortest path. We only need that we reroute flow onto a sufficiently short path. More
precisely, it is easy to convert the proof of Lemma 4.2 into a proof for the following claim.
Lemma 4.9 Suppose oe i and - satisfy the granularity condition and let P be a flow path of commodity
i. Let Q be a path connecting the endpoints of P such that the length of Q is no more than ffl 0 '(P )=2
greater than the length of the shortest path connecting the same endpoints. Then rerouting
units of flow from path P to Q decreases j'j 1 by \Omega\Gamma oe i
We will now show that in order to compute the lengths of paths up to the precision given in this
lemma, we only need to compute the lengths of edges up to a reasonably small amount of precision.
By Lemma 4.9, the length of a path can have a rounding error of ffl 0 jf j
Each path has at
most n edges, so it will suffice to ensure that each edge has a rounding error of 1
now bound this quantity. jf j is the maximum flow on an edge and hence must be at least as large
as the average flow on an edge, i.e. jf j -
vw f(vw)=m. Every unit of flow contributes to the total
flow on at least one edge, and hence
combining with the previous equation,
we get that jf j=D - 1=m. j'j 1 is at least as big as the length of the longest edge, i.e. j'j 1 - e ffjf j .
Plugging in these bounds we see that it suffices to compute with an error of at most ffl 0
Each
edge has a positive length of at most e ffjf j and can be expressed as e ffjf j ae, where 1. Thus we
need to compute ae up to an error of ffl 0
nm . To do so, we need to compute O(log(ffl \Gamma1 nm)) bits which
by the assumption that ffl is inverse polynomial in n is just O(log n) bits.
By using the Taylor series expansion of e x , we can compute one bit of the length function
in O(1) time. Therefore, to compute the lengths of all edges at each iteration of Reduce, we
need O(m log n) time. In the deterministic implementation of Reduce each iteration takes at least
log n) time (the time required for cycle cancelling), therefore the time spent on computing the
lengths is dominated by the running time of an iteration.
The approximation above depends on the current value of jf j, which may change after each
iteration. It was crucial that we recomputed the lengths of every edge in every iteration. The
time to do so, O(m log n), would dominate the running time of the randomized implementation of
Reduce. (Recall that the randomized implementation does not do cycle cancelling.) Thus, we need
to find an approximation which does not need to be recomputed at every iteration. We will choose
one which does not depend on the current jf j and hence will only need to be updated on the O(n)
edges on which the flow actually changes. We proceed to describe such an approximation which will
depend on - rather than jf j.
Throughout Reduce all edge length are at most e O(ff-) , and at least one edge has length more
than e ff- . Therefore, j'j 1 is at least e ff- , and by the same argument as for the deterministic case
bits of precision suffice throughout Reduce. When we first call Reduce, we must spend
time to compute all the edge lengths. For each subsequent iteration, we only need to
updating the O(n) edges whose length has changed. Since each iteration
of Reduce is expected to take O(ffl time to compute shortest paths in FindPath,
the time for updating edges is dominated by the time required by FindPath. While it appears that
the time to initially compute all the edge lengths may dominate the time spent in one invocation of
Reduce, we shall see in Section 5 that whenever any of our algorithms calls Reduce, it will have
at least \Omega\Gammast/ n) iterations. Each iteration is expected to take at
m) time to compute the
shortest paths in FindPath. Therefore, the time spent on initializing lengths will be dominated by
the running time of Reduce.
Note that in describing the randomized version of FindPath in Lemma 4.6, we assumed we
knew the exact lengths. However, by using the approximate lengths we do not significantly change a
path's apparent contribution to the sum
Hence we do not significantly reduce
the probability of selecting a bad path.
Thus we have shown that without any assumptions, Reduce can be implemented deterministically
in the same time as is stated in Theorem 4.8. Although for the randomized version, there is
additional initialization time, for all the algorithms in this paper that initialization time is dominated
by the time spent in the iterations of Reduce.
Theorem 4.10 The times required for the deterministic implementations of procedure Reduce stated
in Theorem 4.8 hold without the assumption that exponentiation is a single step. The time required by the
randomized implementations increases by an additive factor of O(ffl log n) without this assumption.
4.3.2 Further improvements for fixed ffl
In this section we show how one can reduce the time per iteration of Reduce for the case in which
ffl is a constant. First we show how using approximate lengths can reduce the time required by
FindPath; we use an approximate shortest-paths algorithm that runs in O(m
we give improved implementation details for an iteration of Reduce to decrease the time required
by other parts of Reduce.
We will describe how, given the lengths and an ffl-bad path P from s to t, we can find a path
Q with the same endpoints such that '(Q) - dist ' (s; First, we
discard all edges with length greater than '(P ), for they can never be in a path that is shorter than P
(if P is a shortest path between s and t then P is not an ffl-bad path). Next, on the remaining graph,
we compute shortest paths from s using approximate edge-lengths ~
2n d'(vw) 2n
e, thus
giving us dist ~
an approximation of dist ' (s; t), the length of the actual shortest (s; t)-path.
There are at most n \Gamma 1 edges on any shortest path, and for each such edge, the approximate length
is at most ffl 0 '(P )
more than the actual length. Thus we know that
dist ~
since each shortest path length is an integer multiple of ffl 0 '(P )
2n , and no more than '(P ), we
can use Dial's implementation of Dijkstra's algorithm [2] to compute dist ~
Implementing FindPath with this approximate shortest path computation directly improves the
time required by a deterministic implementation of Reduce. The randomized implementation of
FindPath with approximate shortest path computation requires O(ffl expected time.
In order to claim that an iteration of Reduce can be implemented in the same amount of time,
we must handle two difficulties, updating edge lengths and updating each edge's table of flow paths
when flow is rerouted. Previously, these steps took O(n log n) time, which was dominated by the time
for FindPath. We have reduced the time for FindPath, so the time for these steps now dominates.
We show how to carry out these steps in O(n) time. For the first step, we show that a table can
be precomputed so that each edge length can be updated in constant time. For the second step, we
sketch a three-level data structure that allows selection of a random flow path through an edge in
O(n) time, and allows constant-time addition and deletion of flow paths.
Say that before computing the length e fff(vw) , we were to round fff(vw) to the nearest multiple
of ffl=c, for some constant c. This will introduce an additional multiplicative error of
the length of each edge and hence an additional multiplicative error of 1 + O(ffl=c) on each path.
However, by arguments similar to the previous subsection, this will still give us a sufficiently precise
approximation.
Now we will show, that by rounding in this way there are a small enough number of possible
values for '(vw) that we can just compute them all at the beginning of an iteration of Reduce and
then compute the length of an edge by simply looking up the value in a precomputed table. The
largest value of fff(vw) we ever encounter is O(ffl \Gamma1 log n). Since we are only concerned with multiples
of ffl=c, there are a total of only O(ffl \Gamma2 log n) values, we will ever encounter. At the beginning of each
iteration, we can compute each of these numbers to a precision of O(log n) bits in O(ffl \Gamma2 log 2 n) time.
Once we have computed all these numbers, we can compute the length of an edge by computing
fff(vw), truncating to a multiple of ffl=c and then looking up the value of '(vw) in the table. This
takes O(1) time. Thus for constant ffl, we are spending O(log 2 n
Now we address the problem of maintaining, for each edge, the flow paths going through that
edge. Henceforth we will describe the data structure associated with a single edge. First suppose
that all the flow paths carry the same amount of flow, i.e. oe i is the same for each. In this case, we
keep pointers to the flow paths in an array. We maintain that the array is at most one-quarter empty.
It is then easy to randomly select a flow path in constant expected time; one randomly chooses an
index and checks whether the corresponding array entry has a pointer to a flow path. If so, select
that flow path. If not, try another index.
One can delete flow paths from the array in constant time. If one maintains a list of empty
entries, one can also insert in constant time. If the array gets too full, copy its contents into a new
array of twice the size. The time required for copying can be amortized over the time required for
the insertions that filled the array. If the array gets too empty, copy its contents into a new array of
half the size. The time required for copying can be amortized over the time required for the deletions
that emptied the array. (See, for example, [1], for a detailed description of this data structure.)
Now we consider the more general case, in which the flow values of flow paths may vary. In this
case, we use a three-level data structure. In the top level, the paths are organized according to their
starting nodes. In the second level, the paths with a common starting node are organized according
to their ending nodes. The paths with the same starting and ending nodes may be assumed to
belong to the same commodity and hence all carry the same amount of flow. Thus these paths can
be organized using the array as described above.
The first level consists of a list; each list item specifies a starting node, the total flow of all flow
paths with that starting node, and a pointer to the second-level data structure organizing the flow
paths with the given starting node. Each second-level data structure consists of a list; each list item
specifies an ending node, the total flow of all flow paths with that ending node and the given starting
node, and a pointer to the third-level data structure, the array containing flow paths with the given
starting and ending nodes.
Now we analyze the time required to maintain this data structure. Adding and deleting a flow
path takes constant time. Choosing a random flow path with the right probability can be accomplished
in O(n) time. First we randomly choose a value between 0 and the total flow through the
edge. Then we scan the first-level list to select an appropriate item based on the value. Next we
scan the second-level list pointed to by that item, and select an item in the second-level list. Each
of these two steps takes O(n) time. Finally, we select an entry in the third-level array. In the third
level array, all the flows have the same oe i , thus this can be accomplished in O(1) expected time by
the scheme described above.
So we have shown that for constant ffl, each of the three steps in procedure Reduce can be
implemented in O(m) expected time, thus yielding the following theorem.
Theorem 4.11 Let f = O(-) and - and oe i satisfy the granularity condition. Let H(k; d;
and let -
g. For any constant ffl ? 0 the procedure Reduce can
be implemented in randomized O(mH(k; d; oe)) and in deterministic O(H(k; d; oe)m(logn
5 Concurrent flow algorithms
In this section, we give approximation algorithms for the concurrent flow problem with uniform
capacities. We describe two algorithms: Concurrent and ScalingConcurrent. Concurrent
is simpler and is best if ffl is constant. ScalingConcurrent gradually scales ffl to the right value,
and is faster for small ffl.
Algorithm Concurrent (see Figure 2) consists of a sequence of calls to procedure Reduce
described in the previous section. The initial flow is constructed by routing each commodity i on a
single flow path from s i to t i . Initially, we set oe Before each call to Reduce we divide the
flow quantum oe i by 2 for every commodity where this is needed to satisfy the granularity condition
(3). Each call to Reduce modifies the multicommodity flow f so that either jf j decreases by a factor
of 2 or f becomes ffl-optimal. (The procedure Reduce can set a global flag to indicate whether it
has concluded that f is ffl-optimal.) In the latter case our algorithm can terminate and return the
flow. As we will see, O(log m) calls to Reduce will suffice to achieve ffl-optimality.
Theorem 5.1 The algorithm Concurrent finds an ffl-optimal multicommodity flow in
log n), or in expected time
log n) log n).
Immediately after the initialization we have jf j - D. To bound the number of phases we
need a lower bound on the minimum value of jf j. Observe that for every multicommodity flow f ,
the total amount of flow in the network is D. Every unit of flow contributes to the total flow on at
Concurrent(G; ffl; fd(i); (s
For each commodity i: oe i / d(i), create a simple path from s i to t i and route d(i) flow on it.
While f is not ffl-optimal,
For every i,
Until oe i and - satisfy the granularity condition,
Call Reduce(f; -; ffl; d).
-=2.
Return f .

Figure

2: Procedure Concurrent.
least one of the edges, and hence
Therefore,
This implies that the number of iterations of the main loop of Concurrent is at most O(log m).
By Theorems 4.3 and 4.8, procedure Reduce invoked during a single iteration of Concurrent
first spends O(m log n) time initializing edge lengths and then executes O(ffl \Gamma1 minfD;kd(i)g
iterations.
Throughout the algorithm oe i is either equal to d(i), or is \Theta(ffl 2 -= log(mffl \Gamma1 )) for every i. In the first
case,
min fD; kd(i)g
ae D
oe
In the second case
min fD; kd(i)g
log(mffl
Thus the total number of iterations of the loop of Reduce is at most O(ffl
log(mffl
and the time spent on the initialization the edge length is dominated. The value - is halved at every
iteration, therefore the total number of calls required for all iterations is at most O(ffl \Gamma1 k log n) plus
twice the number required for the last iteration of Concurrent. It follows from (4) that - is \Omega\Gamma D
and the total number of iterations of the loop of Reduce is at most O(ffl \Gamma1 k log n+ ffl \Gamma3 m log n).
Consider the special case when ffl is constant. We use the version of Reduce implemented with
an approximate shortest path computation, and apply the bounds of Theorem 4.11 combined with
a proof similar to that of Theorem 5.1 to get the following result:
Theorem 5.2 For any constant ffl ? 0, an ffl-optimal solution for the unit-capacity concurrent flow
problem can be found in O(m(k+ m) log 2 n) expected time by a randomized algorithm and in O(m(k
log d max g) log n) time by a deterministic algorithm.
If ffl is less than a constant, we use the algorithm ScalingConcurrent, shown in Figure 3.
It starts with a large ffl, and then gradually scales ffl down to the required value. More precisely,
algorithm ScalingConcurrent starts by applying algorithm Concurrent with
Concurrent then repeatedly divides ffl by a factor of 2 and calls Reduce. After the initial call
to Concurrent, f is 1-optimal, i.e. jf j is no more than twice the minimum possible value.
Therefore, jf j cannot be decreased below -=2, and every subsequent call to Reduce returns an
ffl-optimal multicommodity flow (with the current value of ffl). As in Concurrent, each call to
Reduce uses the largest flow quantum oe permitted by the granularity condition (3).
f be the resulting flow.
-=2.
While ffl ? ffl 0 ,
For every i,
Until oe i and - satisfy the granularity condition,
Call Reduce(f; -; ffl; oe).
Return f .

Figure

3: Procedure ScalingConcurrent.
Theorem 5.3 The algorithm ScalingConcurrent finds an ffl-optimal multicommodity flow in expected
As is stated in Theorem 5.2, the call to procedure Concurrent takes O(km log n+m 2 log m)
time, and returns a multicommodity flow f that is 1
-optimal, hence jf j is no more than twice the
minimum. Therefore every subsequent call to Reduce returns an ffl-optimal multicommodity flow f .
The time required by one iteration is dominated by the call to Reduce. The input flow f of
Reduce is 2ffl-optimal, so, by Theorems 4.8 and 4.10, the time required by the randomized implementation
of Reduce is O(ffl
We have seen that max i
is
at most O(k+ ffl \Gamma2 m log m). The value of ffl is reduced by a factor of two in every iteration. Therefore,
the total time required for all iterations is at most twice the time required by the last iteration. The
last iteration takes O((k which proves the claim.
Consider an implementation of Concurrent or ScalingConcurrent with the deterministic
version of Reduce. The time required by FindPath does not depend on ffl, so we can not claim that
the time is bounded by at most twice the time required for the last call to Reduce. Since there are
at most log ffl \Gamma1 iterations, we have the following theorem.
Theorem 5.4 An ffl-optimal solution to the unit-capacity concurrent flow problem can be found deterministically
in time O(km log 2 n+(k log ffl log n)(k   n log n+m(log n+min fk; k   log d max g))).
6 Two applications
In this section we describe two applications of our unit-capacity concurrent flow algorithm. The first
application is to efficiently implement Leighton and Rao's sparsest cut approximation algorithm [11],
and the second application is to approximately minimize channel width in VLSI routing; the second
problem was considered by Raghavan and Thompson [13] and Raghavan [12].
We start by reviewing the result of Leighton and Rao concerning finding an approximately sparsest
cut in a graph. For any partition of the nodes of a graph G into two sets A and B, the associated
cut is the set of edges between A and B, and ffi (A; B) denotes the number of edges in that cut. A cut
is sparsest if ffi (A; B)=(jAjjBj) is minimized. Leighton and Rao [11] gave an O(log n)-approximation
algorithm for finding the sparsest cut of a graph. By applying this algorithm they obtained polylog-
times-optimal approximation algorithms for a wide variety of NP-complete graph problems, including
minimum feedback arc set, minimum cut linear arrangement, and minimum area layout.
Leighton and Rao exploited the following connection between sparsest cuts and concurrent flow.
Consider an all-pairs multicommodity flow in G, where there is a unit of demand between every
pair of nodes. In a feasible flow f , for any partition A [ B of the nodes of G, a total of at least
jAjjBj units of flow must cross the cut between A and B. Consequently, one such edge must carry
at least jAjjBj=ffi(A; B) flow for the sparsest cut A [ B. Leighton and Rao prove an approximate
max-flow, min-cut theorem for the all-pairs concurrent flow problem, by showing that in fact this
lower bound for jf j is at most an O(log n) factor below the minimum value. Their approximate
sparsest-cut algorithm makes use of this connection. More precisely given a nearly optimal length
function (dual variables) they show how to find a partition A[B that is within a factor of O(log n)
of the minimum value of jf j, and hence of the value of the sparsest cut. 1
The computational bottleneck of their method is solving a unit-capacity concurrent flow problem,
in which there is a demand of 1 between every pair of nodes. In their paper, they appealed to the fact
that concurrent flow can be formulated as a linear program, and hence can be solved in polynomial
time. A much more efficient approach is to use our unit-capacity approximation algorithm. The
number of commodities required is O(n 2 ). Leighton [10] has discovered a technique to reduce the
number of commodities required. He shows that if the graph in which there is an edge connecting
each source-sink pair is an expander graph, then the resulting flow problem suffices for the purpose
of finding an approximately sparsest cut. (We call this graph the demand graph.) In an expander
we have:
For any partition of the node set into A and B, where jAj - jBj, the number of commodities
crossing the associated cut is '(jAj).
Therefore the value of jf j for this smaller flow problem is \Omega\Gamma jAj=ffi(A; B)). Since jBj - n=2, it follows
that njf j is \Omega\Gamma jAjjBj)=ffi(A; B)). The smaller flow problem essentially "simulates" the original all-pairs
problem. Moreover, Leighton and Rao's sparsest-cut algorithm can start with the length function
for the smaller flow problem in place of that for the all-pairs problem. Thus Leighton's idea allows
one to find an approximate sparsest-cut after solving a much smaller concurrent flow problem. If one
is willing to tolerate a small probability of error in the approximation, one can use O(n) randomly
selected source-sink pairs for the commodities. It is well known how to randomly select node pairs
so that, with high probability, the resulting demand graph is an expander.
By Theorem 5.2, algorithm Concurrent takes expected time O(m 2 log 2 m) to find an appropriate
solution for this smaller problem.
Theorem 6.1 An O(log n)-factor approximation to the sparsest cut in a graph can be found by a
randomized algorithm in O(m 2 log 2 m) time.
The second application we discuss is approximately minimizing channel width in VLSI routing.
Often a VLSI design consists of a collection of modules separated by channels; the modules are
connected up by wires that are routed through the channels. For purposes of regularity the channels
have uniform width. It is desirable to minimize that width in order to minimize the total area of
the VLSI circuit. Raghavan and Thompson [13] give an approximation algorithm for minimizing the
channel width. They model the problem as a graph problem in which one must route wires between
pairs of nodes in a graph G so as to minimize the maximum number of wires routed through an
edge. To approximately solve the problem, they first solve a concurrent flow problem where there is
a commodity with demand 1 for each path that needs to be routed. An optimal solution f opt fails
Their algorithm also works for edge-weighted graphs; weights translate to edge capacities in the corresponding
concurrent flow problem.
to be a wire routing only in that it may consist of paths of fractional flow. However, the value of
jf opt j is certainly a lower bound on the minimum channel width. Raghavan and Thompson give a
randomized method for converting the fractional flow f opt to an integral flow, increasing the channel
width only slightly. The resulting wire routing f achieves channel width
jf opt j log n) (5)
which is at most w min
w min log n), where w min is the minimum width. In fact, the constant
implicit in this bound is quite small. Later Raghavan [12] showed how this conversion method can
be made deterministic.
The computational bottleneck is, once again, solving a unit-capacity concurrent flow problem.
Theorems 5.3 and 5.4 are applicable, and yield good algorithms. But if w min
n), we can
do substantially better. 2 In this case, a modified version of our algorithm ScalingConcurrent
directly yields an integral f satisfying (5), although the big-Oh constant is not as good as that of
[13].
Consider the procedure ScalingConcurrent. It consists of two parts. First the procedure
Concurrent is called
to achieve 1
-optimality. Next, ScalingConcurrent repeatedly
calls Reduce, reducing the error parameter ffl by a factor of two every iteration, till the required
accuracy is achieved. The demands are the same for every commodity, hence oe i is independent of i,
and we shall denote it by oe.
We claim that if w
\Omega\Gamma207 n) then oe, which is initially 1 for this application, need never
be reduced. Consequently, there remains a single path of flow per commodity, and the randomized
conversion method of Raghavan and Thompson becomes unnecessary. We show that these paths
constitute a routing with width w min
w min log n).
First suppose the call to Concurrent terminates because the granularity condition becomes
false. At this point, we have that
We have that - jf j=2 and
n). By our assumption that w
\Omega\Gamma/54 n), and hence jf
w min log n).
Now assume that the call to Concurrent terminates with a 1
-optimal flow. We proceed with
ScalingConcurrent. It terminates when the granularity condition becomes false, at which point
inequality (6) implies that ffl The flow f is ffl-optimal and integral. So jf
O(w min
this bound on jf j is at most w min +O(
w min log m),
as required.
Theorem 6.2 If w min denotes the minimum possible width and w min
=\Omega\Gamma407 m), a routing of width
w min log n) can be found by a randomized algorithm in expected time O(km log n log k
k 3=2 (m+n log n)=
log n), and by a deterministic algorithm in time O(k log k(k   n log n+mk   +m log n)).
We have shown that algorithm ScalingConcurrent finds the required routing if it is
terminated as soon as the granularity condition becomes false with oe = 1. Now we analyze the time
required.
We have every i, and throughout the algorithm we have oe
i. The number of calls to Reduce during Concurrent is O(log (initially jf j - k, and it never
gets below 1 with 1). Therefore the number iterations of the loop of Reduce required during
2 This is the case of most interst, for if wmin is o(log n), then the error term in (5) dominates wmin .
Concurrent is O(k log k). Next we proceed with ScalingConcurrent. The number of iterations
is at most O(log k), because ffl is reduced by a factor of two each iteration, ffl starts at 1
and never
gets below 1=k. Each iteration is a call to Reduce, which in turn results in O(k) iterations of the
loop of Reduce.
The time required by one iteration of the loop deterministically is O(k   n log n +m(k   log m)),
and the total time to find a good routing of wires is O(k log k(k   n log
The expected time required by the randomized implementation of Reduce is O(m log n
n)). The total expected time required by Concurrent is O(mk log k log n). After
the call to Concurrent ffl decreases by a factor of two each iteration, it follows that the total
expected time required for all iterations is O(m log n log ffl \Gamma1 ) plus twice the time for the last call to
Reduce. During the last call to Reduce, ffl
k= log n), so the time required for all iterations
is O(km log n log
log n). This time dominates the time required by
Concurrent since w min
=\Omega\Gamma200 n) implies k
n).

Acknowledgments

We are grateful to Andrew Goldberg, Tom Leighton, Satish Rao, David Shmoys, and Pravin Vaidya
for helpful discussions.



--R

Introduction to Algorithms.
Algorithm 360: Shortest path forest with topological ordering.
Fibonacci heaps and their uses in improved network optimization algorithms.
Solving minimum-cost flow problems by successive approxi- mation
Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems.
Fast algorithms for convex quadratic programming and multicommodity flows.
Approximation through multicommodity flow.



An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms
Probabilistic construction of deterministic algorithms: approximating packing integer programs.
Provably good routing in graphs: regular arrays.
Ordering problems approximated: single-processsor scheduling and interval graph completion
The maximum concurrent flow problem.
A data structure for dynamic trees.
Improved approximation algorithm for concurrent multi-commodity flows
Speeding up linear programming using fast matrix multiplication.
--TR

--CTR
Suh-Wen Chiou, A combinatorial approximation algorithm for concurrent flow problem and its application, Computers and Operations Research, v.32 n.4, p.1007-1035, April 2005
X.-H. Jia , D.-Z. Du , X.-D. Hu , H.-J. Huang , D.-Y. Li, Optimal placement of wavelength converters in WDM networks for parallel and distributed computing systems, Optical networks: recent advances, Kluwer Academic Publishers, Norwell, MA, 2001
Marie-Christine Costa , Alain Hertz , Michel Mittaz, Bounds and Heuristics for the Shortest Capacitated Paths Problem, Journal of Heuristics, v.8 n.4, p.449-465, July 2002
Anil Kamath , Omri Palmon , Serge Plotkin, Fast approximation algorithm for minimum cost multicommodity flow, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.493-501, January 22-24, 1995, San Francisco, California, United States
George Karakostas, Faster approximation schemes for fractional multicommodity flow problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.166-173, January 06-08, 2002, San Francisco, California
Philip Klein , Hsueh-I Lu, Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.338-347, May 22-24, 1996, Philadelphia, Pennsylvania, United States
Neal E. Young, Randomized rounding without solving the linear program, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.170-178, January 22-24, 1995, San Francisco, California, United States
David Karger , Serge Plotkin, Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.18-25, May 29-June 01, 1995, Las Vegas, Nevada, United States
Matthew Andrews , Kyomin Jung , Alexander Stolyar, Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Ashish Goel , Monika R. Henzinger , Serge Plotkin, Online througput-competitive algorithm for multicast routing and admission control, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.97-106, January 25-27, 1998, San Francisco, California, United States
Ashish Goel , Monika R. Henzinger , Serge Plotkin, An online throughput-competitive algorithm for multicast routing and admission control, Journal of Algorithms, v.55 n.1, p.1-20, April 2005
Prabhakar Raghavan , Eli Upfal, Efficient routing in all-optical networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.134-143, May 23-25, 1994, Montreal, Quebec, Canada
Anil Kamath , Omri Palmon , Serge Plotkin, Routing and admission control in general topology networks with Poisson arrivals, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 28-30, 1996, Atlanta, Georgia, United States
Lisa Fleischer, A fast approximation scheme for fractional covering problems with variable upper bounds, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997
Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999
David R. Karger , Clifford Stein, A new approach to the minimum cut problem, Journal of the ACM (JACM), v.43 n.4, p.601-640, July 1996
approximation;multicommodity flow;VLSI routing;concurrent flow;graph separators