3-DIMENSIONAL AXIAL ASSIGNMENT PROBLEMS WITH DECOMPOSABLE COST COEFFICIENTS

Given three n-element sequences a(i), b(i) and c(i) of nonnegative rea l numbers, the aim is to find two permutations phi and psi such that t he sum Sigma(i=1)(n) = a(i)b(phi(i))c(psi(i)) is minimized (maximized, respectively). We show that the maximization version of this problem can be solved in polynomial time, whereas we present an NP-completenes s proof for the minimization version. We identify several special case s of the minimization problem which can be solved in polynomial time, and suggest a local search heuristic for the general case.