Solving minimum-cost flow problems by successive approximation

ABSTRACT

We introduce a framework for solving minimum-cost flow problems. Our approach measures the quality of a solution by the amount that the complementary slackness conditions are violated. We show how to extend techniques developed for the maximum flow problem to improve the quality of a solution. This framework allows us to achieve &Ogr;(min(n3, n5/3 m2/3, nm log n) log (nC)) running time.

REFERENCES

• 1: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 2: C. A. B~tesox~. Perform~x~ce comparison of two algorithms for weighted bipartite matchings. 1985. M.S. thesis, University of Colorado, Boulder, Colorado.
• 3: D. P. Bertsekas. Distributed asynchronous relaxation methods for linear network flow problems. In Proc. ~Sth IEEE Conference on Decision and Control, Athens, Greece, 1986.
• 4: Dimitri P. Bertsekas , Paul Tseng, Relaxation methods for minimum cost ordinary and generalized network flow problems, Operations Research, v.36 n.1, p.93-114, January-February 1988 [doi>10.1287/opre.36.1.93]
• 5: R. G. Bland and D. L. Jensen. On the Computational Behavior of a Polynomial-Time Network Flow Algorithm. Technical Report 661, School of Operations Research and Industrial Engineering, Cornell University, 1985.
• 6: E. A. Dinic. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Dok., 11:1277-1280, 1970.
• 7: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 8: L. R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, N J., 1962.
• 9: Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
• 10: M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses. In Proc. 25th IEEE Syrnp. on Foundations of Computer Science, pages 338-346, 1984.
• 11: S Fujishige, A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm, Mathematical Programming: Series A and B, v.35 n.3, p.298-308, July 1986 [doi>10.1007/BF01580882]
• 12: D. R. Fulkerson. An out-of-kilter method for minireal cost flow problems. SIAM J. Appl. Math, 9:18-27, 1961.
• 13: Harold N. Gabow, Scaling algorithms for network problems, Journal of Computer and System Sciences, v.31 n.2, p.148-168, Sept. 1985 [doi>10.1016/0022-0000(85)90039-X]
• 14: Z. Galil. An O(VS/aE2/a) algorithm for the maximal flow problem. Acta Informatica, 14:221-242, 1980.
• 15: Z. Galil. Personal communication. 1987.
• 16: Z.Galil. and E.Tardos An 0(n2hpoi poop opop ) min-cost flow algorithm. In Proc. ~7ttl IEEE Syrup. of Foundations of Computer Science, pages 1-9, 1986.
• 17: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 18: Saul I. Gass, Linear programming: methods and applications (5th ed.), McGraw-Hill, Inc., New York, NY, 1985
• 19: A. ~. Goldberg. Efficient Graph Algorithms }or Sequential and Parallel Computers. PhD thesis, M.I.T., 1987.
• 20: A V Goldberg , R E Tarjan, A new approach to the maximum flow problem, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.136-146, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12144]
• 21: A. V. Ka:rzanov. Determining the maximal flow in a network by the method of preflows. Soviet Math. Dok., 15:434-437, 1974.
• 22: E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Reinhart, and Winston, New York, NY., 1976.
• 23: C. Leiserson and B. M~ggs. Communication-effident parallel graph algorithms, in Proc. of International Conference on Parallel Processing, p~ges 861-868, 1986.
• 24: V. M. Malhotra, M. Pramodh Kumar, and S. N. Mah~shwa~i. A, o(IvP) algorithm for finding ma~ximum flows in networks, inform. Process. Lett., 7:277-278, 1978.
• 25: G. J. Minty. Monotone networks. Proc. Ro~t. Soc. London, A(257):194-212, 1960.
• 26: A. T. Ogielski. Integer optimization and zerotemperature fixed point in Ising random-field systems. Physical Review Lett., 57(10):1251-1254, 1986.
• 27: J. B. Orlin. Genuinely Polynomial Simplex and Non- Simplex Algorithms for the Minimum Cost Flow Problem. TechnicM Report No. 1615-84, Slosh School of Management, MIT, December 1984.
• 28: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 29: H. RSck. Scaling techniques for minimal cost network flows. In V. Page, editor, Discrete Structures and At. gorithms, C~rl Hansen, Munich, 1980.
• 30: Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
• 31: D. V. Sleator. An O(nmlogn) Algorithm for Maxi. mum Network Flow. Technical Report STAN-CS-80- 831, Computer Science Department, Stanford University, Stantbrd, CA, 1980.
• 32: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 33: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 34: Éva Tardos, A strongly polynomial minimum cost circulation algorithm, Combinatorica, v.5 n.3, p.247-255, 1985 [doi>10.1007/BF02579369]
• 35: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 36: R. E. Tarjan. A simple version of Karzanov's blocking flow algorithm. Operations Research Letters, 2:265- 268, 1984.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification