APPROXIMATION ALGORITHMS FOR MULTIINDEX TRANSPORTATION PROBLEMS WITH DECOMPOSABLE COSTS

The axial multi-index transportation problem is defined as follows. Gi ven are k sets A(r), each set having n(r) elements, r = 1,..., k. The cartesian product of the sets A(r) is denoted by A. To each element a is an element of A a certain cost, c(a) is an element of R, is associa ted. Further, a nonnegative demand e(ri) is associated to each set A(r i) = {a is an element of A : a(r) = i}. The problem is to find nonnega tive real numbers x(a) such that each demand is satisfied (that is Sig ma(a is an element of Ari) x(a) = e(ri) for r = 1,...,k, i = 1,..., n( r)) and such that total cost (that is Sigma(a is an element of A)c(a). x(a)) is minimized. In this paper we deal with a special case of this problem where the costs c, are decomposable, that is, given a real-val ued function f and a distance d(ij)(ArxAs) between element i of A(r) a nd element j of A(s), we assume that c(a) = f(d(a(1),a(2))(A1xA2),..., d(a(k-1),a(k))(Ak-1xAk)) for all a is an element of 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 th e diameter cost-function (that is C-a = max(r,s) d(a(r,a(s))(ArxAs)), and in the case where f-is theHamiltonian path cost-function (that is c(a) = min{Sigma(i=1)(k-1)d(a(sigma(i),a(sigma(i+1)))(A sigma(i)xA sig ma(i+1)) : sigma is a cyclic permutation of {1,...,k}).