Approximation algorithms for three-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 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.].
- Approximation algorithms for multi-dimensional assignment problems with decomposable costs
- The approximability of three-dimensional assignment problems with bottleneck objective
- scientific article; zbMATH DE number 1202983
- Geometric three-dimensional assignment problems
- Geometric versions of the three-dimensional assignment problem under general norms
- A bilinear programming formulation of the 3-dimensional assignment problem
- An Algorithm for Solving 3-Dimensional Assignment Problems with Application to Scheduling a Teaching Practice
- Facets of the three-index assignment polytope
- scientific article; zbMATH DE number 3482073 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- Throughput rate optimization in the automated assembly of printed circuit boards
- An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors
- Lower bounds for the axial three-index assignment problem
- Geometric three-dimensional assignment problems
- Approximation algorithms for multi-dimensional assignment problems with decomposable costs
- Approximation algorithms for multi-index transportation problems with decomposable costs
- Using Approximation Algorithms to Build Evidence Factors and Related Designs for Observational Studies
- approxmatch
- Geometric versions of the three-dimensional assignment problem under general norms
- Test problem generator for the multidimensional assignment problem
- Scheduling sports competitions on multiple venues.
- Three-dimensional axial assignment problems with decomposable cost coefficients
- Scheduling jobs of equal length: Complexity, facets and computational results
- Between a rock and a hard place: the two-to-one assignment problem
- Combining solutions of the axial assignment problem
- Heuristic strategies for combining solutions of the three-index axial assignment problem
- On a property of a three-dimensional matrix
- Integer programming models for the multidimensional assignment problem with star costs
- Multi-index transport problems with decomposition structure
- A heuristic method for solving integer-valued decompositional multiindex problems
- Multi-dimensional vector assignment problems
- Fast separation for the three-index assignment problem
- The focus of attention problem
- Branch and bound solution of the multidimensional assignment problem formulation of data association
- Between a rock and a hard place: the two-to-one assignment problem
- The three-dimensional matching problem in kalmanson matrices
- Local search heuristics for the multidimensional assignment problem
- The three dimensional bottleneck assignment problem and its variants
- Multiindex transportation problems with 2-embedded structure
- scientific article; zbMATH DE number 1202983 (Why is no real title available?)
- Dynamic discrete tomography
- A Simultaneous Magnanti-Wong Method to Accelerate Benders Decomposition for the Metropolitan Container Transportation Problem
- Efficient algorithms for three‐dimensional axial and planar random assignment problems
- On Asymptotically Optimal Algorithm for One Modification of Planar 3-dimensional Assignment Problem
- Local search heuristics for the multidimensional assignment problem
- On optimality of a polynomial algorithm for random linear multidimensional assignment problem
- Approximate search for known gene clusters in new genomes using PQ-trees
- Three-index linear programs with nested structure
- Criteria convolutions when combining the solutions of the multicriteria axial assignment problem
- A new design for observational studies applied to the study of the effects of high school football on cognition late in life
- Solution approaches to the three-index assignment problem
- A hybrid genetic algorithm for the three-index assignment problem
- The approximability of three-dimensional assignment problems with bottleneck objective
- A survey for the quadratic assignment problem
This page was built for publication: Approximation algorithms for three-dimensional assignment problems with triangle inequalities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q139206)
