research-article

Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

Author:

Aleksander MadryAuthors Info & Claims

STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

Pages 121 - 130

https://doi.org/10.1145/1806689.1806708

Published: 05 June 2010 Publication History

Abstract

We combine the work of Garg and Konemann, and Fleischer with ideas from dynamic graph algorithms to obtain faster (1-ε)-approximation schemes for various versions of the multicommodity flow problem. In particular, if ε is moderately small and the size of every number used in the input instance is polynomially bounded, the running times of our algorithms match -- up to poly-logarithmic factors and some provably optimal terms -- the Ω(mn) flow-decomposition barrier for single-commodity flow.

References

[1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows: theory, algorithms, and applications. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993.

Digital Library

[2]

S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: A meta-algorithm and applications. Available at http://www.cs.princeton.edu/arora/pubs/MWsurvey.pdf.

[3]

G. Ausiello, G. F. Italiano, A. M. Spaccamela, and U. Nanni. On-line computation of minimal and maximal length paths. Theoretical Computer Science, 95(2):245--261, 1992.

Digital Library

[4]

S. Baswana, R. Hariharan, and S. Sen. Maintaining all-pairs approximate shortest paths under deletion of edges. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 394--403, Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics.

Digital Library

[5]

S. Baswana, R. Hariharan, and S. Sen. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. Journal of Algorithms, 62(2):74--92, 2007.

Digital Library

[6]

D. Bienstock and G. Iyengar. Solving fractional packing problems in ~O(1/ε) iterations. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 146--155, New York, NY, USA, 2004. ACM.

Digital Library

[7]

C. Demetrescu and G. F. Italiano. Fully dynamic transitive closure: breaking through the o(n<sup>2</sup>) barrier. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, page 381, Washington, DC, USA, 2000. IEEE Computer Society.

Digital Library

[8]

C. Demetrescu and G. F. Italiano. A new approach to dynamic all pairs shortest paths. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 159--166, New York, NY, USA, 2003. ACM.

Digital Library

[9]

C. Demetrescu and G. F. Italiano. Fully dynamic all pairs shortest paths with real edge weights. Journal of Computer and System Sciences, 72(5):813--837, 2006.

Digital Library

[10]

S. Even and Y. Shiloach. An on-line edge-deletion problem. Journal of ACM, 28(1):1--4, 1981.

Digital Library

[11]

L. K. Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal of Discrete Mathematics, 13(4):505--520, 2000.

Digital Library

[12]

N. Garg and J. Konemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pages 300--309, 1998.

Digital Library

[13]

A. V. Goldberg. A natural randomization strategy for multicommodity flow and related algorithms. Information Processing Letters, 42(5):249--256, 1992.

Digital Library

[14]

A. V. Goldberg and S. Rao. Beyond the flow decomposition barrier. Journal of ACM, 45(5):783--797, 1998.

Digital Library

[15]

M. D. Grigoriadis and L. G. Khachiyan. Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM Journal on Optimization, 4(1):86--107, 1994.

[16]

M. D. Grigoriadis and L. G. Khachiyan. Approximate minimum-cost multicommodity flows in~O(ε<sup>{-2}</sup>knm) time. Mathematical Programming, 75(3):477--482, 1996.

Digital Library

[17]

G. Karakostas. Faster approximation schemes for fractional multicommodity flow problems. In Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms, pages 166--173, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics.

Digital Library

[18]

D. Karger and S. Plotkin. Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 18--25, New York, NY, USA, 1995. ACM.

Digital Library

[19]

P. Klein, S. Plotkin, C. Stein, and E. Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM Journal on Computing, 23(3):466--487, 1994.

Digital Library

[20]

P. Klein and N. Young. On the number of iterations for dantzig-wolfe optimization and packing-covering approximation algorithms. In Proceedings of the 7th International IPCO Conference, pages 320--327. Springer, 2002.

Digital Library

[21]

T. Leighton, F. Makedon, S. Plotkin, C. Stein, E. Tardos, and S. Tragoudas. Fast approximation algorithms for multicommodity flow problems. Journal of Computer and System Sciences, 50(2):228--243, 1995.

Digital Library

[22]

A. Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. arXiv:1003.5907. Available at http://arxiv.org/abs/1003.5907

[23]

Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127--152, 2005.

Digital Library

[24]

Y. Nesterov. Fast gradient methods for network flow problems. In The 20th International Symposium of Mathematical Programming, 2009.

[25]

S. A. Plotkin, D. B. Shmoys, and E. Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20:257--301, 1995.

[26]

T. Radzik. Fast deterministic approximation for the multicommodity flow problem. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 486--492, Philadelphia, PA, USA, 1995. Society for Industrial and Applied Mathematics.

Digital Library

[27]

L. Roditty and U. Zwick. Improved dynamic reachability algorithms for directed graphs. In Proceedings of the 43rd Symposium on Foundations of Computer Science, page 679, Washington, DC, USA, 2002. IEEE Computer Society.

Digital Library

[28]

L. Roditty and U. Zwick. Dynamic approximate all-pairs shortest paths in undirected graphs. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages 499--508, Washington, DC, USA, 2004. IEEE Computer Society.

Digital Library

[29]

L. Roditty and U. Zwick. A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 184--191, New York, NY, USA, 2004. ACM.

Digital Library

[30]

L. Roditty and U. Zwick. On dynamic shortest paths problems. In Proceedings of 12th Annual European Symposium on Algorithms, pages 580--591, 2004.

[31]

F. Shahrokhi and D. W. Matula. The maximum concurrent flow problem. Journal of ACM, 37(2):318--334, 1990.

Digital Library

[32]

D. B. Shmoys. Cut problems and their application to divide-and-conquer. pages 192--235, 1997.

Digital Library

[33]

N. E. Young. Randomized rounding without solving the linear program. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 170--178, Philadelphia, PA, USA, 1995. Society for Industrial and Applied Mathematics.

Digital Library

Cited By

Chuzhoy JKhanna SMohar BShinkar IO'Donnell R(2024)Maximum Bipartite Matching in 𝑛2+𝑜(1) Time via a Combinatorial AlgorithmProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649725(83-94)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649725
Haeupler BLong YSaranurak T(2024)Dynamic Deterministic Constant-Approximate Distance Oracles with $n^{\epsilon}$ Worst-Case Update Time2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00121(2033-2044)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00121
Van Den Brand JChen LKyng RLiu YMeierhans SGutenberg MSachdeva S(2024)Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00120(2010-2032)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00120
Show More Cited By

Index Terms

Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Faster approximation schemes for fractional multicommodity flow problems

We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of the minimum possible dependencies on the number of commodities k. We show that by modifying the algorithms by Garg and Könemann [1998] and ...
Fast Approximation Algorithms for Multicommodity Flow Problems

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms uses a fast matrix multiplication algorithm and takes O(k3.5n3m0.5 log(nDU)) time for the ...
Faster approximation schemes for fractional multicommodity flow problems
SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time independent of the number of commodities k. We show that by modifying the algorithms by Garg & Könemann [5] and Fleischer [3] we can reduce ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

June 2010

812 pages

ISBN:9781450300506

DOI:10.1145/1806689

General Chair:
Michael Mitzenmacher
Harvard
,
Program Chair:
Leonard J. Schulman
Caltech

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'10

Sponsor:

SIGACT

STOC'10: Symposium on Theory of Computing

June 5 - 8, 2010

Massachusetts, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
487
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chuzhoy JKhanna SMohar BShinkar IO'Donnell R(2024)Maximum Bipartite Matching in 𝑛2+𝑜(1) Time via a Combinatorial AlgorithmProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649725(83-94)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649725
Haeupler BLong YSaranurak T(2024)Dynamic Deterministic Constant-Approximate Distance Oracles with $n^{\epsilon}$ Worst-Case Update Time2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00121(2033-2044)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00121
Van Den Brand JChen LKyng RLiu YMeierhans SGutenberg MSachdeva S(2024)Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00120(2010-2032)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00120
Forster SNazari YProbst Gutenberg MSaha BServedio R(2023)Deterministic Incremental APSP with Polylogarithmic Update Time and StretchProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585213(1173-1186)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585213
Abboud ALi JPanigrahi DSaranurak T(2023)All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00137(2204-2212)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00137
van Den Brand JZhang D(2023)Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00036(493-502)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00036
Bernstein AGutenberg MSaranurak T(2022)Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00100(1000-1008)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00100
Djaker AKechar BAfifi HMoungla H(2022)Maximum Concurrent Flow Solutions for Improved Routing in IoT Future NetworksArabian Journal for Science and Engineering10.1007/s13369-022-07479-w48:8(10079-10098)Online publication date: 22-Nov-2022
https://doi.org/10.1007/s13369-022-07479-w
Chuzhoy JSaranurak TMarx D(2021)Deterministic algorithms for decremental shortest paths via layered core decompositionProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458211(2478-2496)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458211
Chechik SZhang TMarx D(2021)Incremental single source shortest paths in sparse digraphsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458210(2463-2477)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458210
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents