Approximation algorithms for three-dimensional assignment problems with triangle inequalities

Approximation algorithms for three-dimensional assignment problems with triangle inequalities

0.00 Avg rating0 Votes
Article ID: iaor1996615
Country: Netherlands
Volume: 60
Issue: 3
Start Page Number: 273
End Page Number: 279
Publication Date: Aug 1992
Journal: European Journal of Operational Research
Authors: ,
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. The authors 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 equ1) or the sum of the lengths of its two shortest sides (problemequ2). They prove that equ3 and equ4 are NP-hard. For both equ5 and equ6, the authors present equ7- and equ8-approximate algorithms, i.e. heuristics which always deliver a feasible solution whose cost is at mostequ9, resp.equ10, of the optimal cost. Computational experiments indicate that the performance of these heuristics is excellent on randomly generated instances of equ11 and equ12.

Reviews

Required fields are marked *. Your email address will not be published.