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 language | English (US) |
|---|---|
| Pages | S981-S982 |
| State | Published - 1999 |
| Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999 |
Other
| Other | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| City | Baltimore, MD, USA |
| Period | 1/17/99 → 1/19/99 |
All Science Journal Classification (ASJC) codes
- Software
- General Mathematics