A MONGE PROPERTY FOR THE D-DIMENSIONAL TRANSPORTATION PROBLEM

In 1963, Hoffman gave necessary and sufficient conditions under which a family of O (mn)time greedy algorithms solves the classical two-dime nsional transportation problem with m sources and n sinks, One member of this family, an algorithm based on the ''northwest corner rule'', i s of particular interest, as its running time is easily reduced to O ( m + n). When restricted to this algorithm, Hoffman's result can be exp ressed as follows: the northwest-corner-rule greedy algorithm solves t he two-dimensional transportation problem for all source and supply ve ctors if and only if the problem's cost array C = {c[i,j]} possesses w hat is known as the (two-dimensional) Monge property, which requires c [i(1),j(1)] + c[i(2),j(2)] less than or equal to c[i(1),j(2)] + c[i(2) ,j(1)] for i(1) < i(2) and j(1) < j(2), This paper generalizes this la st result to a higher dimensional variant of the transportation proble m, We show that the natural extension of the northwest-corner-rule gre edy algorithm solves an instance of the d-dimensional transportation p roblem if and only if the problem's cost array possesses a d-dimension al Monge property recently proposed by Aggarwal and Park in the contex t of their study of monotone arrays. We also give several new examples of cost arrays with this d-dimensional Monge property.