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$

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.