Efficient algorithms for the Hitchcock transportation problem

ABSTRACT

We consider the Hitchcock transportation problem on n supply points and k demand points when n is much greater than k. The problem is solved in O(n2k log n + n2 log2 n) time if n > k log k. Further, applying a geometric method named splitter finding and randomization, we improve the time complexity for a case in which the ratio c of the least supply and the maximum supply satisfies the inequality log cn < n/k4 log n. Indeed, if n < k5 log3 k and c = poly(n), the problem is solved in O(kn) time, which is optimal.

REFERENCES

• 1: Ahuja, R. K., Orlin, J. B., Stein, C., Tarjan, R. E., Improved Algorithms for Bipartite Network Flow, Preprint (1991).
• 2: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 3: 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]
• 4: 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]
• 5: Galil, Z. and Tardos, E., An O(n2(m + n log n)log n) Min-cost Flow Algorithm, Proc. 27th iEEE FOCS pp.136-146, (1986).
• 6: Haussler, D. and Welzl, E., e-nets and simplex range queries, Disc. Comp. Geom. ~ pp.127-151, (1987).
• 7: Matsui, T., Linear Time Algorithm for Hitchcock Transportation problem with Fixed Number of Supply Points, Preprint (1991).
• 8: Kazumiti Numata , Takeshi Tokuyama, Splitting a configuration in a simplex, Proceedings of the international symposium on Algorithms, p.429-438, August 1990, Tokyo, Japan
• 9: James Orlin, A faster strongly polynomial minimum cost flow algorithm, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.377-387, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62249]
• 10: Éva Tardos, A strongly polynomial minimum cost circulation algorithm, Combinatorica, v.5 n.3, p.247-255, 1985 [doi>10.1007/BF02579369]
• 11: Takeshi Tokuyama , Jun Nakano, Geometric algorithms for a minimum cost assignment problem, Proceedings of the seventh annual symposium on Computational geometry, p.262-271, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109678]
• 12: Tokuyama, T. and Nakano, J., Unpublished result.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Theory, Verification