Fast and simple approximation schemes for generalized flow

Fast and simple approximation schemes for generalized flow

0.00 Avg rating0 Votes
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: ,
Abstract:

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 n2, where n is the number of nodes. This is accomplished in part by introducing an efficient method of solving a sequence of generalized shortest path problems. Our generalized multicommodity FPTASs are now as fast as the best non-generalized ones. We believe our improvements make it practical to solve generalized multicommodity flow problems via combinatorial methods.

Reviews

Required fields are marked *. Your email address will not be published.