Approximation algorithms for multi-index transportation problems with decomposable costs Original Research Article

The axial multi-index transportation problem is defined as follows. Given are k sets Ar, each set having nr elements, r = 1, …, k. The cartesian product of the sets Ar is denoted by A. To each element a ϵ A a certain cost, ca ϵ R, is associated. Further, a nonnegative demand eri is associated to each set Ari = [a ϵ A : a(r) = i]. The problem is to find nonnegative real numbers xa such that each demand is satisfied (that is ∑aϵAri xa = eri for r = 1, …, k, i = 1, …,nr) and such that total cost (that is ∑aϵAca · xa) is minimized.