Fast and simple approximation schemes for generalized flow |
| |
Authors: | Lisa K. Fleischer Kevin D. Wayne |
| |
Affiliation: | (1) GSIA, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15217. Partially supported by NSF through grants DMS 95-27124, and EIA-0049084. e-mail: lkf@andrew.cmu.edu, US;(2) Computer Science Department, Princeton University, Princeton, NJ 08544. Research supported in part by ONR through grant AASERT N00014-97-1-0681. e-mail: wayne@cs.princeton.edu, US |
| |
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 FPTAS’s for traditional multicommodity flow and packing linear programs. Our FPTAS’s dominate the previous best known complexity bounds for all of these problems, some by more than a factor of n 2, 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 FPTAS’s 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. Received: June 3, 1999 / Accepted: May 22, 2001?Published online September 17, 2001 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|