RECOGNITION OF D-DIMENSIONAL MONGE ARRAYS

It is known that the d-dimensional axial transportation (assignment) p roblem can easily be solved by a greedy algorithm if and only if the u nderlying cost array fulfills the d-dimensional Monge property. In thi s paper the following question is solved: Is it possible to find d per mutations in such a way that the permuted array becomes a Monge array? Furthermore we give an algorithm which constructs such permutations i n the affirmative case. If the cost array has the dimensions n1 x n2 x ... x n(d) with n1 less-than-or-equal-to n2 less-than-or-equal-to ... less-than-or-equal-to n(d), then the algorithm has time complexity O( d2n2 ... n(d)(n1 + log n(d))). By using this algorithm a wider class o f d-dimensional axial transportation problems and in particular of the d-dimensional axial assignment problems can be solved efficiently.