\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


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


Shortest Augmenting Path


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


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


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!


Finish remarks on min-cost flow.