Faster approximation algorithms for generalized flow

Kevin Wayne, Lisa Fleischer

Research output: Contribution to conferencePaperpeer-review

12 Scopus citations

Abstract

We present faster FPTAS's for generalized versions of the maximum flow, multicommodity flow, minimum cost flow, and minimum cost multicommodity flow problems in lossy networks. We dominate the previous best known complexity bounds for all of these problems, some by as much as a factor of n2. Our generalized multicommodity FPTAS's are now as fast as the best non-generalized ones. We give a O(m2) time FPTAS for the generalized maximum flow problem. This is faster than the previous best strongly-polynomial bound by a factor of n. We are also able to reduce the dependency on the error parameter from ε-2 to log(1/ε) in this case.

Original languageEnglish (US)
StatePublished - Jan 1 1999
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Faster approximation algorithms for generalized flow'. Together they form a unique fingerprint.

Cite this