Reference : Approximation algorithms for three-dimensional assignment problems with triangle ineq...
Scientific journals : Article
Business & economic sciences : Quantitative methods in economics & management
Physical, chemical, mathematical & earth Sciences : Mathematics
Approximation algorithms for three-dimensional assignment problems with triangle inequalities
Crama, Yves mailto [Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production >]
Spieksma, Frits C.R. []
European Journal of Operational Research
Elsevier Science
Yes (verified by ORBi)
The Netherlands
[en] 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Δ .

File(s) associated to this reference

Fulltext file(s):

Restricted access
EJOR1992_3DAMpaper.pdfPublisher postprint456.61 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.