Combinatorial Approximation Algorithms for Generalized Flow Problems

✍ Scribed by Jeffrey D Oldham

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 226 KB
• Volume: 38
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2000.1130

✦ Synopsis

Generalized network flow problems generalize normal network flow problems by specifying a flow multiplier µ v w for each arc v w . For every unit of flow entering the arc, µ v w units of flow exit. We present a strongly polynomial algorithm for a single-source generalized shortest paths problem, using a left-distributive closed semiring. This permits use of a dynamic-programming routine similar to the Bellman-Ford algorithm, given a guess for the value of the optimal solution. Using Megiddo's parametric search scheme, we can compute the optimal value in strongly polynomial time. The algorithm's running time O mn 2 log n matches the previously best known, but the algorithm is simpler, is based on the well-known theory of closed semirings, and directly works with the given graph. All previous polynomialtime algorithms were based on interior-point methods or directly solved the dual problem and translated the solution back to the primal problem. Using this generalized shortest paths algorithm, we present fully polynomial-time approximation schemes for the generalized versions of the maximum flow, the nonnegative-cost minimum-cost flow, the concurrent flow, the multicommodity maximum flow, and the multicommodity nonnegative-cost minimum-cost flow problems with running times independent of the size of the flow multipliers' representation.