Approximation algorithms for three-dimensional assignment problems with triangle inequalities

Consider the following classical formulation of the (axial) three-dimensional assignment problem (3DA) (see e.g. Balas and Saltzman (1989)). Given is a complete tripartite graph K _{n,n, n} = (I∪J∪K,(I × J) ∪ (I × K) ∪ (J × K)), where I, J, K are disjoint sets of size n, and a cost c _ijk for each triangle (i, j, k) ∈ I × J × K. The problem 3DA is to find a subset A of n triangles, A⊆ I × J × K, such that every element of I ∪ J ∪ K occurs in exactly one triangle of A, and the total cost c(A) = ∑_(i,j,k)∈Ac _ijk is minimized. Some recent references to this problem are Balas and Saltzman (1989), Frieze (1974), Frieze and Yadegar (1981), Hansen and Kaufman (1973).