4
$\begingroup$

I am taking linear optimization class. Could you suggest me good fundamental textbook on advanced topics of network flows. To be more specific I am interested in: Multicommodity flow and multicut, the flow/cut gap theorem, algorithm CKR/FRT, concarent flow and sparse cut, embedding graph metrics into random trees.

Before stating network flows, I was using few great books on operations reseach and linear programming. But none of them covers such topics. Vanderbei's and Rader's book end up on max-flow min-cut theorem, Bazaraa's book goes further and covers multicommodity flows.

  • 0
    Good paper on very advanced level was found here [An improved approximation algorithm for the 0-extension problem](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.123.2508), enough for motivation, but if you know an explanation on lower lever maybe video lecture, I will appreciate posting a link.2011-12-02
  • 0
    [The Design of Approximation Algorithms](http://www.designofapproxalgs.com/), [Approximation Algorithms](http://books.google.com/books?vid=ISBN3540653678)2011-12-03
  • 0
    The classic text on network flows is *Network Flows*, by Ahuja, Magnanti, and Orlin. It's about 20 years old, though. I don't know of a more recent text.2011-12-06

1 Answers 1

1

Great question.

Try this:

R.T. Rockafellar, Network Flows and Monotropic Optimization, J. Wiley, (1984).

Rockafellar is a reknowned expert in optimisation. His books and materials are excellent examples of clarity and build quickly from an overview to advanced topics in network theory.

If you go to his website, he has kindly made the full text of this book and many of his papers and course lecture notes available as PDF downloads.