• 6.5210/18.415: Advanced Algorithms
  • PSets
  • Calendar
  • Materials
  • Information
  • Min Cost Flow

    David Karger

    Gross flow formulation (otherwise double-count).

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

    Clearly, generalizes max-flow. Also shortest path:

    Min-cost circulation:

    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.

    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.

    Feasible prices certify a min-cost flow

    Price function is a general concept


    Shortest Augmenting Path


    Idea: augmenting paths

    Claim: shortest augmenting path doesn’t create negative cycles

    Alternative correctness argument: use price function.

    Is SAP strongly polynomial for MCF?

    Special case algorithm:

    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)

    Cost Scaling


    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.