Approximation algorithms for three-dimensional assignment problems with triangle inequalities (Q139206): Difference between revisions

The three-dimensional assignment problem (3DA) is defined as follows. Given are three disjoint \(n\)-sets of points, and nonnegative costs associated with each triangle consisting of exactly one point from each set. The problem is to find a minimum-weight collection of a 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\). Extensions of the previous results to the \(k\)-dimensional case \((k\geq 3)\) were obtained by \textit{H.-J. Bandelt, Y. Crama} and \textit{F. C. Spieksma}, ``Approximation algorithms for multidimensional assignment problems with decomposable costs'' [to appear in Discrete Appl. Math.].