HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Literature on network-flow (optimization) approximation algorithms

Submitted by: @import:stackexchange-cs··
0
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.

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.