On Monge sequences in d-dimensional arrays

AbstractLet C be an n × m matrix. Then the sequence j:= ((i1, j1), (i2, j2), …, (inm, jnm)) of pairs of indices is called a Monge sequence with respect to the given matrix C if and only if, whenever (i, j) precedes both (i, s) and (r, j) in j, then c[i, j] + c[r, s] ≤ c[i, s] + c[r, j]. Monge sequences play an important role in greedily solvable transportation problems. Hoffman showed that the greedy algorithm which maximizes all variables along a sequence j in turn solves the classical Hitchcock transportation problem for all supply and demand vectors if and only if j is a Monge sequence with respect to the cost matrix C. In this paper we generalize Hoffman's approach to higher dimensions. We first introduce the concept of a d-dimensional Monge sequence. Then we show that the d-dimensional axial transportation problem is solved to optimality for arbitrary right-hand sides if and only if the sequence j applied in the greedy algorithm is a d-dimensional Monge sequence. Finally we present an algorithm for obtaining a d-dimensional Monge sequence which runs in polynomial time for fixed d