A Scaling Algorithm for Multicommodity Flow Problems

References

• Ahuja R. K., Orlin J. B., Tarjan R. E. Improved time bounds for the maximum flow problem. SIAM J. Comput. (1989) 18:939–954Crossref, Google Scholar
• Ahuja R. K., Goldberg A. V., Orlin J. B., Tarjan R. E. Finding minimum-cost flows by double scaling. Math. Programming (1992) 53:243–266Crossref, Google Scholar
• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows—Theory, Algorithms, and Applications (1993) (Prentice-Hall, Inc., Englewood Cliffs, NJ) Google Scholar
• Ali I., Barnett D., Farhangian K., Kennington J., Patty B., Shetty B., McCarl B., Wong P. Multicommodity network problems: Applications and computations. IIE Trans. (1984) 16:127–134Crossref, Google Scholar
• Ali A., Helgason R., Kennington J., Lall H. Computational comparison among three multicommodity network flow algorithms. Opns. Res. (1980) 28:995–1000Link, Google Scholar
• Assad A. A. Multicommodity network flows—Computational experience. (1976) . Working paper OR-058-76, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Assad A. A. Multicommodity network flows—A survey. Networks (1978) 8:37–91Crossref, Google Scholar
• Avriel M.Nonlinear Programming: Analysis and Methods (1976) (Prentice-Hall, Inc., Englewood Cliffs, NJ) Google Scholar
• Barnhart C. A network-based primal-dual solution methodology for the multicommodity network flow problem. (1988) . Ph.D. thesis, Department of Civil Engineering, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Barnhart C. Dual-ascent methods for large-scale multicommodity flow problems. Naval Res. Logist. Q. (1993) 40:305–324Crossref, Google Scholar
• Barnhart C., Sheffi Y. A network-based primal-dual heuristic for the solution of multicommodity network flow problems. Trans. Sci. (1993) 27(2):102–117Link, Google Scholar
• Bertsimas D., Orlin J. B. A technique for speeding up the solution of the Lagrangean dual. (1991) . Working paper no. 3278-91, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Choi I. C., Goldfarb D., Coleman T., Li Q. Solving multicommodity network flow problems by an interior point method. Proc. SIAM Workshop Large-Scale Numerical Optim. (1989) Google Scholar
• Dinic E. A. The method of scaling and transportation problems. Issledovaniya po Diskretnoi Matematike (1973) (Science, Moscow) . in RussianGoogle Scholar
• Edmonds J., Karp R. M. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM (1972) 19:248–264Crossref, Google Scholar
• Fiacco A. V., McCormick G. P.Nonlinear Programming: Sequential Unconstrained Minimization Techniques (1968) (John-Wiley & Sons, New York) Google Scholar
• Farvolden J. M., Powell W. B. A primal partitioning solution for multicommodity network flow problems. (1990) . Working paper #90-04, Department of Industrial Engineering, University of Toronto, Toronto, CanadaGoogle Scholar
• Farvolden J. M., Powell W. B., Lustig I. J. A primal partitioning solution for the arc-chain formulation of a multicommodity network flow problem. Opns. Res. (1993) 41(4):669–693Link, Google Scholar
• Ford L. R., Fulkerson D. R.Flows in Networks (1962) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Frank M., Wolfe P. An algorithm for quadratic programming. Naval Res. Logist (1956) 3:95–110Crossref, Google Scholar
• Gabow H. Scaling algorithms for network problems. J. Comput. System Sci. (1985) 31:148–168Crossref, Google Scholar
• Goldberg A. V., Tarjan R. E. Solving minimum cost flow problems by successive approximation. Proc. 19th ACM Sympos. Theory Comput. (1987) 7–18Crossref, Google Scholar
• Grigoriadis M. D., Khachiyan L. G. Fast approximation schemes for convex programs with many blocks and coupling constraints. (1991) . Technical report DCS-TR-273, Department of Computer Science, Rutgers University, New Brunswick, NJGoogle Scholar
• Kennington J. L. A survey of linear cost multicommodity network flows. Opns. Res. (1978) 26:209–236Link, Google Scholar
• Klein P., Agrawal A., Ravi R., Rao S. Approximation through multicommodity flow. Proc. 31st Annual Sympos. Foundations Comput. Sci. (1990a) 726–727Crossref, Google Scholar
• Klein P., Plotkin S. A., Stein C., Tardos E. Fast approximation algorithms for the unit capacity concurrent flow problem with application to routing and finding sparse cuts. Proc. 22nd Annual ACM Sympos. Theory Comput. (1990b) 310–321Also Technical report 961, School of Operations Research and Industrial Engineering, Cornell University, New York, 1991Google Scholar
• Leighton T., Makedon F., Plotkin S., Stein C., Tardos E., Tragoudas S. Fast approximation algorithms for multicommodity flow problems. Proc. 23rd Annual ACM Sympos. Theory Comput. (1991) 101–111Crossref, Google Scholar
• Luenberger D. G.Linear and Nonlinear Programming (1984) (Addison-Wesley, Reading, MA) Google Scholar
• Orlin J. B. A faster strongly polynomial minimum cost flow algorithm. Proc. 20th ACM Sympos. Theory Comput. (1988) 377–387Crossref, Google Scholar
• Pinar M. C., Zenios S. A. Parallel decomposition of multicommodity network flows using smooth penalty functions. (1990) . Report 90-12-06, Decision Sciences Department, The Wharton School, University of Pennsylvania, Philadelphia, PAGoogle Scholar
• Plotkin S., Shmoys D. B., Tardos E. Fast approximation algorithms for packing and covering problems. Proc. 32nd Annual Sympos. Foundations Comput. Sci. (1991) Crossref, Google Scholar
• Rockafellar R. T.Network Flows and Monotropic Optimization (1984) (John Wiley and Sons, New York) Google Scholar
• Schneur R. Scaling algorithms for multicommodity flow problems and network flow problems with side constraints. (1991) . Ph.D. thesis. Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Shahrokhi F., Matula D. W. The maximum concurrent flow problem. J. ACM (1990) 37:318–334Crossref, Google Scholar
• Sheffi Y.Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods (1976) (Prentice-Hall, Inc., Englewood Cliffs, NJ) Google Scholar
• Vaidya P. M. Speeding up linear programming using fast matrix multiplication. Proc. 30th Annual Sympos. Foundations Comput. Sci. (1989) 332–337Crossref, Google Scholar