APPROXIMATION ALGORITHMS FOR 3-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-DELTA) or the sum of the lengths of its two shortest sides (problem S-DELTA). We prove that T-DELTA and S-DELTA are NP-hard. For both T-DELTA and S-DELTA, 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-DELTA and S-DELTA.