Faster and simpler algorithms for multicommodity flow and other fractional packing problems. (English) Zbl 1137.90014
Summary: This paper considers the problem of designing fast, approximate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We present new, faster, and much simpler algorithms for these problems.
MSC:
| 90C27 | Combinatorial optimization |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C08 | Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) |
| 90C35 | Programming involving graphs or networks |
| 90C59 | Approximation methods and heuristics in mathematical programming |
