Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
Authors:
- Naveen GargNGNaveen Garg
- Jochen KönemannJKJochen Könemann
Top Cited Papers
- 1 January 2007
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 37 (2) , 630-652
Abstract
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.Keywords
This publication has 19 references indexed in Scilit:
- Approximating Fractional Packings and Coverings in O(1/epsilon) IterationsSIAM Journal on Computing, 2006
- Smooth minimization of non-smooth functionsMathematical Programming, 2004
- Fast and simple approximation schemes for generalized flowMathematical Programming, 2002
- Divide-and-conquer approximation algorithms via spreading metricsJournal of the ACM, 2000
- Approximating Fractional Multicommodity Flow Independent of the Number of CommoditiesSIAM Journal on Discrete Mathematics, 2000
- Fast Approximate Graph Partitioning AlgorithmsSIAM Journal on Computing, 1999
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse CutsSIAM Journal on Computing, 1994
- Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling ConstraintsSIAM Journal on Optimization, 1994
- A natural randomization strategy for multicommodity flow and related algorithmsInformation Processing Letters, 1992
- The maximum concurrent flow problemJournal of the ACM, 1990