×

A Monge property for the \(d\)-dimensional transportation problem. (English) Zbl 0833.90083

Summary: In 1963, Hoffman gave necessary and sufficient conditions under which a family of \(O(mn)\)-time greedy algorithms solves the classical two- dimensional transportation problem with \(m\) sources and \(n\) sinks. One member of this family, an algorithm based on the “northwest corner rule”, is of particular interest, as its running time is easily reduced to \(O(m+ n)\). When restricted to this algorithm. Hoffman’s result can be expressed as follows: the northwest-corner-rule greedy algorithm solves the two-dimensional transportation problem for all source and supply vectors if and only if the problem’s cost array \(C= \{c[i, j]\}\) possesses what is known as the (two-dimensional) Monge property, which requires \(c[i_1, j_1]+ c[i_2, j_2]\leq c[i_1, j_2]+ c[i_2, j_1]\) for \(i_1< i_2\) and \(j_1< j_2\). This paper generalizes this last result to a higher-dimensional variant of the transportation problem. We show that the natural extension of the northwest-corner-rule greedy algorithm solves an instance of the \(d\)- dimensional transportation problem if and only if the problem’s cost array possesses a \(d\)-dimensional Monge property recently proposed by Aggarwal and Park in the context of their study of monotone arrays. We also give several new examples of cost arrays with this \(d\)-dimensional Monge property.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90B06 Transportation, logistics and supply chain management
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aggarwal, A.; Klawe, M. M.; Moran, S.; Shor, P. W.; Wilber, R., Geometric applications of a matrixsearching algorithm, Algorithmica, 2, 195-208 (1987) · Zbl 0642.68078
[2] Aggarwal, A.; Park, J. K., (Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (1988)), 497-512, Portions of this paper appear in
[3] Aggarwal, A.; Park, J. K., (Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (1988)), 497-512, Portions of this paper appear in
[4] Aggarwal, A.; Park, J. K., (Research Report RC 15626 (1990), IBM T.J. Watson Research Center: IBM T.J. Watson Research Center Yorktown Heights, NY), An earlier version of this paper appears as · Zbl 0820.90035
[5] Atallah, M. J.; Kosaraju, S. R.; Larmore, L. L.; Miller, G.; Teng, S., Constructing trees in parallel, (Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures (1989)), 421-431
[6] Bein, W. W., Netflows, polymatroids, and greedy structures, (PhD thesis (1986), Universität Osnabrück: Universität Osnabrück Osnabrück)
[7] Submitted to Math. Programming.; Submitted to Math. Programming. · Zbl 0801.90076
[8] Bein, W. W.; Brucker, P.; Pathak, P. K., Monge properties in higher dimensions, (Technical Report CS90-11 (1990), Department of Computer Science, University of New Mexico: Department of Computer Science, University of New Mexico Albuquerque, NM)
[9] Bein, W. W.; Pathak, P. K., A characterization of the Monge property, (Technical Report CS90-10 (1990), Department of Computer Science, University of New Mexico: Department of Computer Science, University of New Mexico Albuquerque, NM) · Zbl 1006.91503
[10] Burkard, R. E., Assignment problems: Recent solution methods and applications, (Prékopa, A.; Szelezsán, J.; Strazicky, B., System Modelling and Optimization: Proceedings of 12th IFIP Conference. System Modelling and Optimization: Proceedings of 12th IFIP Conference, Budapest, Hungary, September 2-6, 1985. System Modelling and Optimization: Proceedings of 12th IFIP Conference. System Modelling and Optimization: Proceedings of 12th IFIP Conference, Budapest, Hungary, September 2-6, 1985, Lecture Notes in Control and Information Sciences, 84 (1986), Springer: Springer New York), 153-169
[11] Cechlárová, K.; Szabó, P., On the Monge property of matrices, Discrete Math., 81, 123-128 (1990) · Zbl 0726.06010
[12] Eppstein, D.; Galil, Z.; Giancarlo, R.; Italiano, G. F., Sparse dynamic programming, (Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (1990)), 513-522 · Zbl 0785.90094
[13] Fahimi, M.; Pathak, P. K., Applications of a size reduction technique for transportation problems in sampling, (Proceedings of the First International Symposium on Optimization and Statistics. Proceedings of the First International Symposium on Optimization and Statistics, Aligarh, India (1989)) · Zbl 0767.62009
[14] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[15] Hoffman, A. J., On simple linear programming problems, (Klee, V., Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the AMS. Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the AMS, Proceedings of Symposia in Pure Mathematics, 7 (1963), American Mathematical Society: American Mathematical Society Providence, RI), 317-327
[16] Larmore, L. L.; Przytycka, T. M., Parallel construction of trees with optimal weighted path length, (Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (1991)), 71-80
[17] Larmore, L. L.; Schieber, B., Ondashline dynamic programming with applications to the prediction of RNA secondary structure, J. Algorithms, 12, 490-515 (1991) · Zbl 0724.90080
[18] Monge, G., Mémoire sur la théorie des déblais et des remblais, (Histoire de l’Académie Royale des Sciences, Année M. DCCLXXXI, avec les Mémoires de Mathématique et de Physique, pour la même Année, Tirés des Registres de cette Académie (1784), L’Imprimerie Royale: L’Imprimerie Royale Paris), 666-704
[19] Orlin, J. B., (Proceedings of the 20th Annual ACM Symposium on Theory of Computing (1988)), 377-387, An earlier version of this paper appears in
[20] Wagner, H. M., On a class of capacitated transportation problems, Management Sci., 5, 304-318 (1959) · Zbl 0995.90513
[21] Yao, F. F., Efficient dynamic programming using quadrangle inequalities, (Proceedings of the 12th Annual ACM Symposium on Theory of Computing (1980)), 429-435
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.