15-750 Graduate Algorithms 3/13/01
- min cost max flow
- min cost circulation
- Klein's cycle canceling
- Goldberg-Tarjan
[This material is not in the book, but Michel Goemans has a nice set
of notes -- see http://www-math.mit.edu/~goemans/. Part of the
discussion below is based on them.]
========================================================================
MIN-COST MAX FLOW
Edges have costs w(e) *and* capacities c(e). Cost of a flow f is
SUM_e w(e)*f(e).
Goal is, out of all max flows, to find the one of least cost.
E.g., can use to solve min-cost perfect matching. (Say we have stores
and factories, each factory can supply k stores, and there are costs
for assigning a given store to a given factory based on the distance
between them).
Will assume all costs (and capacities) are integers.
RESIDUAL GRAPHS: notion of residual graph will be useful as before.
If we push f units of flow on an edge (u,v) of cost w, we will put in
the residual graph an edge (v,u) of capacity f and cost -w. Meaning
of this is that if we undo this flow, we get our money back.
How to solve? One question is: are there any negative cost cycles?
(Even if all edges are positive at the start, residual graphs will
generally have negative cost edges, but we will never introduce
negative cost cycles.) If there are no negative-cost cycles, the
problem is slightly easier. But we'll look at the general problem
(allowing negative-cost cycles) here since it's not that much worse.
Note that this means the optimum solution may have little disjoint
cycles of flow spinning around.
One nice thing to do representationally is to turn this into the "min
cost circulation" problem.
MIN-COST CIRCULATION
In this problem, there is no source or sink. Our goal is just to find
a circulation (every node has inflow = outflow) of least cost. So, if
there are no negative-cost cycles, then best is just not to circulate
anything. But, in general we will saturate all the negative-cost
cycles we find.
Converting min-cost max-flow into min-cost circulation: just put an
edge from t to s of infinite capacity and large negative cost. Then
the min-cost circulation will automatically route as much flow as
possible from s to t in the original graph.
The analog to the Ford-Fulkerson algorithm for this problem is Klein's
Cycle-Canceling algorithm:
While the current residual graph has a negative-cost cycle C,
Push as much flow as possible around C (until edge of minimum
residual capacity is saturated).
(We'll worry about how to *find* such a cycle in a minute)
[Run on flow problem you get from mincost bipartite matching with
A,B,C on the LHS and A',B',C' on the RHS. edge (A,A') has weight 1,
edge (A,B') has weight 2, edge (B,A') has weight 1, edge (B,C') has
weight 2, edge (C,B') has weight 2, edge (C,C') has weight 1.]
Proof of correctness: Analog of Ford-Fulkerson argument is that a
circulation is optimal iff there are no negative-cost cycles in the
residual graph. Obvious direction is that if there *is* a
negative-cost cycle then you're not optimal. Other direction: if f is
not optimal, then there's a better f^*. Now, the key point is that if
you look at f^* - f, this will be a legal circulation in the current
residual graph, and it has negative cost (because everything is
linear). So it must have in it a negative cost cycle.
How to find a negative-cost cycle? Several algorithms. Here's one.
BELLMAN-FORD: Bellman-Ford is a dynamic-programming algorithm that,
given some goal vertex, will find the shortest path from everywhere in
the graph to that goal vertex. The algorithm works as follows: for
each node in the graph, we will compute the length of the shortest path
to the goal that uses i or fewer edges (let's say this length is
infinity if no such path exists). Start with i=0: dist(goal,0)=0,
dist(v,0)=infinity for all v != goal. Then update for i=1, 2, ... by
using dist(v,i) = min_{edges (v,x)} [w(v,x) + dist(x,i-1)]. This
takes O(m) time per iteration. Also, store pointer next(v) to which x
produces the minimum. After n-1 iterations, we have the shortest path of
length n-1 or less, which is the true shortest path so long as there
are no negative-cost cycles.
For our purposes, we want to use this to actually *find* negative-cost
cycles. To do this, we start by picking some goal vertex that is
reachable from everywhere. One easy way to do this is to introduce a
new vertex "g", and create directed edges of cost 0 (the cost doesn't really
matter) from each vertex v to g. Now, we saw from the argument above
that if there are no negative-cost cycles, then
distances will stop changing after i=n-1 and the next(v) pointers will form
a tree. It turns out that if there *is* a negative-cost cycle, the
distances will never stop changing (so we can test if there exists a
negative-cost cycle by seeing if anything changes at step i=n). Here
is the proof of this fact: if we have a step in which no distances
change, that means that along any cycle (v1,v2,...,vk),
dist(v1) <= dist(v2) + w(v1,v2),
dist(v2) <= dist(v3) + w(v2,v3), ...
summing both sides we get that the cost of the cycle is non-negative.
In fact, this implies that at step i=n, the graph of next() pointers
has a cycle [take the node whose shortest path of length n was
detected to be strictly less than its shortest path of length n-1, and
follow its path]. Total time is O(mn).
SPEEDING UP:
The algorithm so far has the same problem as Ford-Fulkerson. To speed
up, the natural approach is to find the "best" augmenting cycle.
E.g., the cycle of least total cost. Unfortunately, that's NP-hard
(can encode Hamiltonian cycle). So, instead, we will find something a
little different.
GOLDBERG-TARJAN:
Define mean cost of a cycle to be the cost of the cycle divided by the
number of edges in it (i.e., the average cost per edge). What we *can*
find is the cycle of minimum mean cost. Idea: add some value k to
weights of all edges and then rerun BF to see if there is still a
negative-cost cycle. The minimum mean cost cycle is the one that
stays negative for the highest value of k. So, can do binary search.
Or, can just use BF directly: minimum mean-cost cycle is the one that
gives most bang per edge, so can detect.
DEF: MM(G_f) is the cost per edge of the minimum mean-cost cycle in G_f.
Goldberg-Tarjan algorithm: Always pick cycle of minimum mean cost in
current residual graph to saturate.
Claim: number of iterations is O(nm*ln(-n*MM(G))).
Before proving, here's a neat idea: vertex potentials. Suppse we give
each vertex v a potential p(v) [think of as a height].
Then, define w_p(u,v) = w(u,v) - p(u) + p(v).
[i.e. we pay (u,v), plus we pay or get back based on whether we are
going uphill or downhill].
What do these do to the cost of cycles? Answer: nothing.
Question: does there exist p such that all edges have w_p(u,v) >= MM(G_f)?
(Note: we can't hope to make a higher lower-bound, because that would
violate the defn of MM(G_f)).
Answer: yes. Let's add k = -MM(G_f) to the weight of each edge, so
now there are no negative-cost cycles. Create some new goal-node g,
with edges of weight 0 for every node to g [the weight doesn't have to
be 0, so long as they are all the same]. Then let p(v) be the length
of the shortest path to g from v [which is now well-defined].
So, for any edge (u,v), p(u) <= [w(u,v)+k] + p(v).
I.e.,
-k <= w(u,v) - p(u) + p(v) = w_p(u,v).
We will use this idea to prove the claim.
PROOF (of bound for GT): Say we currently have residual graph G_f.
Define potentials p as above: w_p(u,v) >= MM(G_f). Now, let's watch
what happens to the edge costs in the residual graph under this
potential. The first cycle found will have all negative-cost edges.
At least one of these gets removed from the residual graph (i.e.,
saturated), and reverse-edges may be put in, but they all have
positive cost (everything here is under potential p). Pretty soon it
must be the case that the next cycle found by our algorithm would have
at least one edge of positive cost (at worst this happens at the mth
iteration, since each prior iteration removes some negative-cost edge
from the graph and adds only positive-cost edges). At this point, say
we have flow f'. This means that MM(G_f') >= ((n-1)*MM(G_f) + 0)/n =
(1 - 1/n)*MM(G_f). I.e., it's gotten closer to 0.
So, every m steps, we've gotten a bit closer to 0. After nm steps
we're closer by a factor of 1/e. After nm*ln(n*MM(G)) steps, MM(G_f')
> -1/n. This means it's actually 0 (since everything is integral),
and we are done!
SPEEDUP: The running time here is not so great. We can do it faster
by explicitly computing potentials p, throwing out all edges of
non-negative cost, and then just working with this graph until there
are no longer any cycles in which all edges have negative cost. Can
get rid of one factor of m this way. Can reduce further with sneaky
data structures.