Write down the dual of the maximum-flow linear program, as given
in lines (29.47)-(29.50). Explain how to interpret this formulation as
a
minimum-cut problem.
Here are lines (29.47)-(29.50):
maximize sum_{v in V} f(s,v)
subject to the following constraints:
f(u,v) <= c(u,v) for each u,v in V
f(u,v) = -f(v,u) for each u,v in V
sum_{v in V} f(u,v) = 0 for each u in V-{s,t}
[This is a more symmetric formulation of the max flow problem in which
we keep flow amounts f(u,v)=-f(u,v) for each pair of vertices, not
just
when there is an edge from u to v; c(u,v) is the capacity if there is
an
edge or zero otherwise. The last constraint line is equivalent to
saying that the flow in equals the flow out.] |
Request for Question Clarification by
mathtalk-ga
on
16 Nov 2002 16:01 PST
Hi, g8z-ga:
I hope you've had a chance to read my answer to your first of the
three questions you posted along these lines, and to note the request
for clarification I left for the second question.
I was reluctant to attempt to reply to this post without having some
feedback from you on those first two. I would guess from the use of
"formula numbers" in your question that you have in hand a book or
other printed reference to provide a good deal of background
information, and perhaps taking this into account someone might be
able to give you a satisfactory explanation of the maximum
flow-minimum cut duality within the constraints of the price you
quoted.
To go from 'first principles' as I did in solving your first question
would necessitate a great deal of writing. A proper presentation
would have to begin by backing up to fill in more notation that the
abbreviated version given in your question. For example, we should
define that s is the unique "source" and t the unique "sink" in the
(directed?) graph G having vertex set V.
To proceed perhaps you could respond to those earlier posts, indicate
the textbook or other reference from which this material is drawn, and
assist us experts in gauging the level of thoroughness with which you
expect the answer to be presented at the listed price.
thanks in advance,
mathtalk-ga
|
Clarification of Question by
g8z-ga
on
17 Nov 2002 12:01 PST
The problem is from CLR (Cormen/Leiserson/Rivest), the newest edition.
There is a section on duality of linear programming in the new edition
(chapter 29 I presume), but this section does not exist in the edition
that I have.
I understand the max-flow/min-cut duality, so I don't need any
background on that, and I have about a semester of algorithm
coursework, so I don't think that you need to go back to first
principles, although I went ahead and increased the price for this
question a little since it seems more involved. See my clarification
on the earlier post, too.
|
