Minimum cost flows over time without intermediate storage

ABSTRACT

Flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. They naturally model problems where travel and transmission are not instantaneous. Solving these problems raises issues that do not arise in standard network flows. One issue is the question of storage of flow at intermediate nodes. In most applications (such as, e.g., traffic routing, evacuation planning, telecommunications etc.), intermediate storage is limited, undesired, or prohibited.The minimum cost flow over time problem is NP-hard. In this paper we 1) prove that the minimum cost flow over time never requires storage; 2) provide the first approximation scheme for minimum cost flows over time that does not require storage; 3) provide the first approximation scheme for minimum cost flows over time that meets hard cost constraints, while approximating only makespan.Our approach is based on a condensed variant of time- expanded networks. It also yields fast approximation schemes with simple solutions for the quickest multicommodity flow problem.Finally, using completely different techniques, we describe a very simple capacity scaling FPAS for the minimum cost flow over time problem when costs are proportional to transit times. The algorithm builds upon our observation about the structure of optimal solutions to this problem: they are universally quickest flows. Again, the FPAS does not use intermediate node storage. In contrast to the preceding algorithms that use a time-expanded network, this FPAS runs directly on the original network.

REFERENCES

• 1: J. E. Aronson, A survey of dynamic network flows, Annals of Operations Research, v.20 n.1-4, p.1-66, Aug. 1989 [doi>10.1007/BF02216922]
• 2: Lisa Fleischer , Martin Skutella, The Quickest Multicommodity Flow Problem, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.36-53, May 27-29, 2002
• 3: L. R. Ford and D. R. Fulkerson. Constructing maximal dynamic flows from static flows. Operations Research, 6:419--433, 1958.
• 4: D. Gale. Transient flows in networks. Michigan Mathematical Journal, 6:59--63, 1959.
• 5: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 6: A. Hall and M. Skutella. Personal communication, 2002.
• 7: Bruce Edward Hoppe, Efficient dynamic network flow algorithms, Cornell University, Ithaca, NY, 1996
• 8: Bruce Hoppe , Éva Tardos, Polynomial time algorithms for some evacuation problems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.433-441, January 23-25, 1994, Arlington, Virginia, United States
• 9: Bruce Hoppe , Òva Tardos, The Quickest Transshipment Problem, Mathematics of Operations Research, v.25 n.1, p.36-62, February 2000 [doi>10.1287/moor.25.1.36.15211]
• 10: Bettina Klinz , Gerhard J. Woeginger, Minimum Cost Dynamic Flows: The Series-Parallel Case, Proceedings of the 4th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.329-343, May 29-31, 1995
• 11: E. Minieka. Maximal, lexicographic, and dynamic network flows. Operations Research, 21:517--527, 1973.
• 12: J. B. Orlin. Minimum convex cost dynamic network flows. Mathematics of Operations Research, 9:190--207, 1984.
• 13: W. B. Powell, P. Jaillet, and A. Odoni. Stochastic and dynamic networks and routing. In M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, editors, Handbooks in Operations Research and Management Science: Networks. Elsevier Science Publishers B. V., 1995.
• 14: W. L. Wilkinson. An algorithm for universal maximal dynamic flows in a network. Operations Research, 19:1602--1612, 1971.
• 15: N. Zadeh. A bad network problem for the simplex method and other minimum cost flow algorithms. Mathematical Programming, 5:255--266, 1973.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Theory