Approximation algorithms for multi-index transportation problems with decomposable costs

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, , 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.

In this paper we deal with a special case of this problem where the costs ca are decomposable, that is, given a real-valued function f and a distance dAr × Asij between element i of Ar and element j of As, we assume that ca = f(dA1 × A2a(1), a(2), …, dAk − 1 × Aka(k−1), a(k)) for all a ϵ A. We present two algorithms for this problem, and we analyze their worst-case behavior without requiring explicit knowledge of the cost-function f. Next, we use these results to derive explicit bounds in the case where f is the diameter cost-function (that is ca = maxr,sdAr × Asa(r),a(s)), and in the case where f is the Hamiltonian path cost-function (that is ca = min [∑k − 1i = 1 dAσ(i) × Aσ(i + 1)a(σ(i)), a(σ(i + σ is a cyclic permutation of [1, …, k]).