Approximation algorithms for three-dimensional assignment problems with triangle inequalities

The three-dimensional assignment problem (3DA) is defined as follows. Given are three disjoint n-sets of points, and nonnegative costs associated with every triangle consisting of exactly one point from each set. The problem is to find a minimum-weight collection of n triangles covering each point exactly once. We consider the special cases of 3DA where a distance (verifying the triangle inequalities) is defined on the set of points, and the cost of a triangle is either the sum of the lengths of its sides (problem TΔ) or the sum of the lengths of its two shortest sides (problem SΔ). We prove that TΔ and SΔ are NP-hard. For both TΔ and SΔ, we present 1 2- and 1 3-approximate algorithms, i.e. heuristics which always deliver a feasible solution whose cost is at most 3 2, resp. 4 3, of the optimal cost. Computational experiments indicate that the performance of these heuristics is excellent on randomly generated instances of TΔ and SΔ.