Approximation algorithms for three-dimensional assignment problems with triangle inequalities

Y. Crama, F.C.R. Spieksma

Research output: Contribution to journalArticleAcademicpeer-review

74 Citations (Scopus)

Abstract

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Δ.

Original languageEnglish
Pages (from-to)273-279
Number of pages7
JournalEuropean Journal of Operational Research
Volume60
Issue number3
DOIs
Publication statusPublished - 10 Aug 1992
Externally publishedYes

Keywords

  • computational analysis
  • heuristics
  • Integer programming
  • three-dimensional assignment

Fingerprint Dive into the research topics of 'Approximation algorithms for three-dimensional assignment problems with triangle inequalities'. Together they form a unique fingerprint.

Cite this