Are there any learning materials of polynomial minimum cost flow algorithms?

Revision en3, by ouuan, 2019-10-29 10:15:15

Many people think they know how to solve the min-cost-max-flow problem, but most of them only know how to solve it with pseudo-polynomial time algorithm (although it usually runs very fast). And in this blog, min_25 provided a counter case generator, most people's MCMF algorithm runs in $$$O(2^{\frac n 2}n^2\log n)$$$ on it.

the counter case

I tried to find learning materials of polynomial minimum cost flow algorithms, but I can only find papers like A Faster Strongly Polynomial Minimum Cost Flow Algorithm and Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, and I can't understand them very well.

Are there any other learning materials besides the papers? Thanks in advance.

UPD. I've learned an algorithm with time complexity of $$$O(m^2\log U\log m)$$$ ($$$U$$$ refers to the maximum capacity), for Chinese and those who want to see my code, I wrote a blog; for those who want English learning materials, the one mentioned in Laakeri's comment is good.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ouuan 2019-10-29 10:15:15 480 add my blog and the notes in Laakeri's comment
en2 English ouuan 2019-10-21 14:56:44 10 Tiny change: ' well.\n\nIs there any' -> ' well.\n\nAre there any'
en1 English ouuan 2019-10-21 14:55:15 9188 Initial revision (published)