patternMinor
Literature on network-flow (optimization) approximation algorithms
Viewed 0 times
flowapproximationliteraturealgorithmsoptimizationnetwork
Problem
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.
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.
Solution
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).
Context
StackExchange Computer Science Q#37413, answer score: 4
Revisions (0)
No revisions yet.