Negative cycle-canceling
Revision as of 04:33, 22 October 2014 by Weihe (talk | contribs) (Created page with "== Abstract view == '''Algorithmic problem:''' Min-cost flow problem '''Type of algorithm:''' loop '''Invariant:''' The flow is feasible. '''Variant:''' The cost of th...")
Abstract view
Algorithmic problem: Min-cost flow problem
Type of algorithm: loop
Invariant: The flow is feasible.
Variant: The cost of the flow decreases.
Definition:' A cycle is negative if the sum of the cost values on all of its arcs is negative.
Break condition: There is no more negative cycle in the residual network.
Induction basis
Abstract view: Start with an arbitrary feasible flow, for example, the zero flow.
Induction step
Abstract view:
- Find a cycle of negative cost in the residual network.
- Augme