§ Min cost flow (TODO)
- Problem statement: Find a maximal flow with minimum cost.
- Find max flow.
- Find negative cost cycle in residual graph of max flow. Push flow around the negative cost cycle.
§ Relation between max flow and min cost circulation
- Recall that min cost circulation asks to compute a circulation with minimum cost [no maximality constraint ].
- Given a flow network ( is capacity fn), create a new cost function which assigns cost zero to all edges in the flow networ. Also add a new edge which has infinite capacity, cost .
- A circulation with cost lower than zero will have to use the edge. To get minimum cost, it must send as much flow through this edge as possible. For it to be a circulation, the full flow in the network must be zero. So suppose we send units of flow back from to . Then we must send units of flow from to for it to be a circulation. Incrasing (max flow) decreases the cost of the circluation! Thus, max flow is reduced to min cost circulation.
§ Min Cost Flow in general
- First find max flow using whatever.
- Next, we need to find negative cost cycle in the residual graph.
- Use bellman ford, or SPFA to find negative cost cycles in time [run edge relaxation times ].
§ Minimum mean cycle
- Which is best cycle to push flow around to reduce cost? The min cost cycle may not be best, since it may have very little capacity.
- A negative cycle with max capacity may not have good cost.
total cost/number of edges --- that is, the mean cost.
§ shortest path as circulation.
- Need to find single source shortest path in a graph (with possibly negative edges, no negative cycles).
- We have a balance at each vertex , which tells us how much extra flow must can have coming in versus going out. So, . Intuitively, the balance is stored in a tank at the vertex.
- We need total balance to be zero.
- We set the source to have balance (supply) and all the other nodes to have balance (demand).
- Let the cost of each edge be the distance, let the capacity of each edge be infinite.
- Now, what is a min cost flow which obeys the demands?
- Consider the shortest path tree. Imagine it as carrying a flow. Then the shortest path tree indeed obeys the flow constraints.
- To convert this into circulation, add back edges from each node back to the source, with a capacity of 1, cost of zero.
- This converts shortest path trees into flows/circulations.
§ Min cost circulation algorithms
- Old algorithm: start with a circulation that obeys balance, then push more around (by using negative cycles)
- New algorithm (successive shortest path): remove all negative cycles, then restore balance constraints.
- how to remove negative cycles? We can just send flow down all negative edges. The resdiual graph will contain no negative cycles. (NOTE: we don't have a valid flow at this point!) This leaves us with resdiual balances at each vertex, about how much more flow we need to send.