1
$\begingroup$

I've been searching on literature on approximation algorithms in the context of network-flow problems (optimization) to finish my bachelor degree.

However, I have been looking in several well-known algorithm books but, I haven't yet found something. Most books don't go beyond Ford-Fulkerson and/or Edmond-Karp in respect to network-flow problems, and the sections explaining approximation algorithms discuss some algorithms not relating to network-flow optimization.

Could someone point me towards appropriate literature? I prefer books instead of papers.

$\endgroup$
  • 1
    $\begingroup$ You might like Schrijver's Combinatorial Optimization, it contains a lot of discussion and references to network flow. I just checked, and e.g. its chapter on maximum flow lists around 20 algorithms. $\endgroup$ – Juho Jun 14 '15 at 9:06
4
$\begingroup$

In his FOCS2013 (Best Paper award) work, Aleksander Mądry gives a $\widetilde O(m^{\frac{10}{7}})$-time for exact max-flow and gives a nice survey on the existing techniques (including near-linear time for $(1+\epsilon)$-approximation in undirected graphs).

$\endgroup$
1
$\begingroup$

There's lots of literature in the computer vision community, as network flow has been used for many purposes. I know I've read survey papers from computer vision folks that compare a number of different algorithms for network flow to figure out which ones work best for computer vision applications.

For one example application, you could look at "seam carving": https://dl.acm.org/citation.cfm?doid=1435417.1435437

$\endgroup$
0
$\begingroup$

The most comprehensive textbook in about network flows, and still a good reference even though it is little bit an old book (published in 1993) but it keeps itself alive:

Network Flows - Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.

It has 19 chapters about different areas and over 800 pages. It is a standard book for the theorist who works on theoretical networks, and also who works on algorithms and applications.

$\endgroup$
  • $\begingroup$ This superficially looks like a reasonable answer, but I can't tell whether it actually answers the question that was asked. Does it have material on approximation algorithms for the network flow problem, as the question requests? $\endgroup$ – D.W. Jun 14 '15 at 6:49
  • $\begingroup$ @D.W. Whether there is an approximation algorithm, I would say "no"; but whether there is an optimization algorithm, I would say "yes"; because the author of the book wrote "The book has the following features: [...] Treatment of other important topics in network optimization and of practical solution techniques such as Lagrangian relaxation"; I hope this helps $\endgroup$ – YOUSEFY Jun 14 '15 at 9:10
  • $\begingroup$ This is not an answer to the question that was asked, then. The question asks specifically for information about approximation algorithms. If the book doesn't have information about that, this doesn't answer the question (and the fact that it has other stuff doesn't change that). This is more suitable as a comment -- please reserve the answer box for information that answers the question. Thank you for your contribution! $\endgroup$ – D.W. Jun 14 '15 at 10:24
  • $\begingroup$ @D.W. Thank you too, for your notices. next time I will comment in the "comment" box, not in "answer" box. I just realized the different now .. $\endgroup$ – YOUSEFY Jun 14 '15 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.