Idea
Round costs to power of 2. Solve optimally. Halve rounding. Solve. Repeat until true costs.
Advertisement
Complexity
O(V³ × log(V × C)) or similar. Strongly polynomial (independent of numerical values).
Advertisement
Practical use
Used in LEDA, CS2 (Goldberg's implementation). Fastest general-purpose MCMF library code.