ON MONGE SEQUENCES IN D-DIMENSIONAL ARRAYS

Let C be an n X m matrix. Then the sequence L = ((i(1),j(1)),(i(2),j(2 )),..., (i(nm),j(nm))) of pairs of indices is called a Monge sequence with respect to the given matrix C if and only if, whenever (i,j) prec edes both (i,s) and (r,j) in L, then c[i,j] + c[r,s] less than or equa l to c[i,s] + c[r,j]. Monge sequences play an important role in greedi ly solvable transportation problems. Hoffman showed that the greedy al gorithm which maximizes all variables along a sequence L in turn solve s the classical Hitchcock transportation problem for all supply and de mand vectors if and only if L is a Monge sequence with respect to the cost matrix C. In this paper we generalize Hoffman's approach to highe r dimensions. We first introduce the concept of a d-dimensional Monge sequence. Then we show that the d-dimensional axial transportation pro blem is solved to optimality for arbitrary right-hand sides if and onl y if the sequence L applied in the greedy algorithm is a d-dimensional Monge sequence. Finally we present an algorithm for obtaining a d-dim ensional Monge sequence which runs in polynomial time for fixed d. (C) 1998 Elsevier Science Inc.