Article ID: | iaor2003720 |
Country: | Germany |
Volume: | 91 |
Issue: | 2 |
Start Page Number: | 215 |
End Page Number: | 238 |
Publication Date: | Jan 2002 |
Journal: | Mathematical Programming |
Authors: | Fleischer L.K., Wayne K.D. |
We present fast and simple fully polynomial-time approximation schemes (FPTAS) for generalized versions of maximum flow, multicommodity flow, minimum cost maximum flow, and minimum cost multicommodity flow. We extend and refine fractional packing frameworks introduced in FPTASs for traditional multicommodity flow and packing linear programs. Our FPTASs dominate the previous best known complexity bounds for all of these problems, some by more than a factor of