\documentclass{article} \usepackage{me} \setlength{\parindent}{0pt}

Min-Cost Flow

Gross flow formulation (otherwise double-count).

Many different max-flows in a graph. How compare?

Clearly, generalizes max-flow. Also shortest path:

2016 L10 start

Min-cost circulation:

2011 Lecture 8 End

Deciding optimality:

Given a max-flow. How decide optimal?

Cycle Canceling Algorithm

(Klein)

Cycle canceling algorithm:

How find negative-cost cycle?

So: time bound of $O(m^2\sqrt{n}CU\log C)$ or $O(nm^2CU)$ time.

Slow, and not even weakly polynomial! Let's do better.

Later (homework), you'll see that cycle canceling is a good idea combined with scaling. But for now, lets take a different approach.

2013 Lecture 11 end

Prices and Reduced Costs

Recall: flow/circulation optimal iff no residual negative cost cycle.

Reduced-Cost optimality.

When is a set of prices “stable”?

Important observation: prices don't affect overall cost:

Claim: A circulation/flow is optimal iff there exists a feasible price function on its residual graph.

Price function is a general concept

Algorithms

Shortest Augmenting Path

Idea:

Idea: augmenting paths

Claim: shortest augmenting path doesn't create negative cycles

Special case algorithm:

Alternative correctness argument: use price function.

Note: don't need explicit prices to run

Limitations:

Lets handle negative arcs.

Handle min-cost flow via max-flow plus above min-cost circulation

Scaling Min-Cost flow

Capacity Scaling

Scale in capacity bits one at a time. (Edmonds Karp 1972)

2012 Lecture 11 End
2013 Lecture 12 End

Cost Scaling

HW

2011 Lecture 9 end
2013 Lecture 13 start

Complementary Slackness

Looking ahead to linear programming.

Complementary slackness is on original graph, corresponds to feasible pricing on residual graph

Given feasible price function, can find opt flow easy:

saw converse: given flow, need to compute optimum distances. So min-cost flow really is max-flow plus shortest paths!

Conclusion

Finish remarks on min-cost flow.