In 1963, Hopman 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[i1,j1]+c[i2,j2]•c[i1,j2]+c[i2,j1] for i1<i2 and j1<j2. This paper generalizes this last result to a higher dimensional variant of the transportation problem. The authors 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. They also give several new examples of cost arrays with this d-dimensional Monge property.
