Faster and simpler algorithms for multicommodity flow and other fractional packing problems

被引：175
作者：
Garg, Naveen [1 ]
Koenemann, Jochen
机构：
[1] Indian Inst Technol, New Delhi, India
[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
来源：
SIAM JOURNAL ON COMPUTING | 2007年 / 37卷 / 02期
关键词：
multicommodity flow; fractional packing; concurrent flow; approximation algorithms;
D O I：
10.1137/S0097539704446232
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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.
引用
收藏
页码：630 / 652
页数：23
相关论文
共 26 条
[1]  
Ahuja R.K., 1993, NETWORK FLOWS THEORY
[2]  
Awerbuch B., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P487, DOI 10.1145/195058.195238
[3]   Approximating fractional packings and coverings in O(1/ε) iterations [J].
Bienstock, D ;
Iyengar, G .
SIAM JOURNAL ON COMPUTING, 2006, 35 (04) :825-854
[4]  
BIENSTOCK D, 2002, POTENTIAL FUNCTION M
[5]   Fast approximate graph partitioning algorithms [J].
Even, G ;
Naor, JS ;
Rao, S ;
Schieber, B .
SIAM JOURNAL ON COMPUTING, 1999, 28 (06) :2187-2214
[6]   Divide-and-conquer approximation algorithms via spreading metrics [J].
Even, G ;
Naor, J ;
Rao, S ;
Schieber, B .
JOURNAL OF THE ACM, 2000, 47 (04) :585-616
[7]   Approximating fractional multicommodity flow independent of the number of commodities [J].
Fleischer, LK .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (04) :505-520
[8]   Fast and simple approximation schemes for generalized flow [J].
Fleischer, LK ;
Wayne, KD .
MATHEMATICAL PROGRAMMING, 2002, 91 (02) :215-238
[9]   Faster and simpler algorithms for multicommodity flow and other fractional packing problems [J].
Garg, N ;
Könemann, J .
39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :300-309
[10]  
GARG N, 1997, 971025 MAX PLANCK I
123