|
Consistent matrix rounding. You have a matrix of floating-point numbers, and you want to round all the numbers
to integers. Each row and column also has a sum, and you’re also going to round those sums. You’re free to choose
whether to round up or down in each case (that is, whether to use math.floor or math.ceil), but you must make sure
that the sum of the round numbers in each row and column is the same as the rounded column or row sum. (You can
see this as a criterion that seeks to preserve some important properties of the original matrix after the rounding.) We
call such a rounding scheme a consistent rounding.
This looks very numerical, right? You might not immediately think of graphs or network flows. Actually, this
problem is easier to solve if we first introduce lower bounds on the flow in each edge, in addition to the capacity
(which is an upper bound). This gives us a new initial hurdle: finding a feasible flow with respect to the bounds.
Once we have a feasible flow, finding a maximum flow can be done with a slight modification of the Ford-Fulkerson
approach, but how do we find this feasible initial flow? This is nowhere near as easy as finding a feasible flow
with respect to supplies and demands. I’ll just sketch out the main idea here—for details, consult Section 4.3 in
Introduction to Graph Theory, by Douglas B. West, or Section 6.7 in Network Flows, by Ahuja et al.
The first step is to add an edge from t to s with infinite capacity (and a lower bound of zero). We now no longer
have a flow network, but instead of looking for a flow, we can look for a circulation. A circulation is just like a flow,
except that it has flow conservation at every node. In other words, there is no source or sink that is exempt from the
conservation. The circulation doesn’t appear somewhere and disappear somewhere else; it just “moves around” in
the network. We still have both upper and lower bounds, so our task is now to find a feasible circulation (which will
give us the feasible flow in the original graph).
If an edge e has lower and upper limits l(e) and u(e), respectively, we define c(e) = u(e) – l(e). (The naming choice
here reflects that we’ll be using this as a capacity in a little while.) Now, for each node v, let l
–
(v) be the sum of the lower
bounds on its in-edges, while l
+
(v) is the sum of the lower bounds on its out-edges. Based on these values, we define b(v)
= l
–
(v) – l
+
(v). Because each lower bound contributes both to its source and target node, the sum of b values is zero.
Now, magically enough, if we find a feasible flow with respect to the capacities c and the supplies and demands
b (as discussed for the previous problem), we will also find a feasible circulation with respect to the lower and upper
bounds l and u. Why is that? A feasible circulation must respect l and u, and the flow into each node much equal
the flow out. If we can find any circulation with those properties, we’re done. Now, let f ’(e) = f (e) – l(e). We can then
enforce the lower and upper bounds on f by simply requiring that 0 £ f ’(e) £ c(e), right?
Now consider the conservation of flow and circulation. We want to make sure that the circulation f into a node
equals the circulation out of that node. Let’s say the total flow f ’ into a node v minus the flow out of v equals b(v)—
exactly the conservation requirement of our supply/demand problem. What happens to f ? Let’s say v has a single
in-edge and a single out-edge. Now, say the in-edge has a lower bound of 3 and the out-edge has a lower bound of 2.
This means that b(v) = 1.
6
We need one more unit of out-flow f ’ than in-flow. Let’s say the in-flow is 0 and the out-flow
is 1. When we transform these flows back to circulations, we have to add the lower bounds, giving us 3 for both the
in-circulation and the out-circulation, so the sum is zero. (If this seems confusing, just try juggling the ideas about
a bit, and I’m sure they’ll “click.”)
Now we know how to find a feasible flow with lower bounds (by first reducing to feasible circulations and then
reducing again to feasible flows with supplies and demands). What does that have to do with matrix rounding?
6
Note that the sum here is the in-edge lower bounds minus the out-edge lower bounds—the opposite of how we sum the flows. That’s
exactly the point.
ChApTeR 10
■
MATChINgs, CuTs, ANd Flows
224
Let x
1
, …, x
Do'stlaringiz bilan baham: |
